bitsetでやれば間に合うというのを知らなかったので解けず。

solution

bitsetを使った速い$O(N^2)$。 $a_i$の値ごとにまとめてやる。 boolの列で持ってやるより$\log \mathrm{UINT\_MAX} \approx 32$倍速いので通る。

はんこの色ごとに独立であるので、それぞれ処理する。 同じ値を持つ$a_{i_1} = a_{i_2} = \dots = a_{i_l}$に関して、これらからまとめてbit列$d = \Sigma_j^{\mathrm{xor}} (b \ll i_j)$を作る。 それぞれの位置に関して何回色の違うはんこが押されたかのbit列$c$に対し、これを$c \gets c \operatorname{xor} d$として更新する。

implementation

#include <cstdio>
#include <bitset>
#include <vector>
#include <map>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
#define N 100000
#define L (2*N-1)
int main() {
    // input
    int n; scanf("%d", &n);
    map<int,vector<int> > a;
    repeat (i,n) {
        int it; scanf("%d", &it);
        a[it].push_back(i);
    }
    bitset<L> b;
    repeat (i,n) {
        int it; scanf("%d", &it);
        b[i] = it;
    }
    // compute
    bitset<L> c;
    for (auto it : a) {
        bitset<L> d;
        for (int i : it.second) {
            d |= b << i;
        }
        c ^= d;
    }
    // output
    repeat (i,2*n-1) {
        printf("%s\n", c[i] ? "ODD" : "EVEN");
    }
    return 0;
}