Yukicoder No.387 ハンコ
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;
}