Submission #3776909
Source Code Expand
#include <vector>
using namespace std;
using u8 = unsigned char;
using uint = unsigned int;
class bitVector {
public:
uint length, cnum, bnum;
static int cw, bw;
vector<uint> bit;
vector<uint> chunk;
vector<vector<u8>> blocks;
explicit bitVector(int N) : length(N) {
cnum = (length + cw - 1) / cw;
bnum = cw / bw;
bit.assign(cnum * bnum, 0);
chunk.assign(cnum + 1, 0);
blocks.assign(cnum, vector<u8>(bnum, 0));
}
void set(int pos, int b) {
int bpos = pos / bw;
int offset = pos % bw;
if (b == 0) {
bit[bpos] &= ~(1 << offset);
} else if (b == 1) {
bit[bpos] |= (1 << offset);
}
}
int access(int pos) const {
int bpos = pos / bw;
int offset = pos % bw;
return bit[bpos] >> offset & 1;
}
uint popCount(uint num) const {
return __builtin_popcount(num);
}
void build() {
chunk[0] = 0;
for (int i = 0; i < cnum; ++i) {
blocks[i][0] = 0;
for (int j = 0; j < bnum - 1; ++j) {
blocks[i][j + 1] = blocks[i][j] + popCount(bit[i * bnum + j]);
}
chunk[i + 1] = chunk[i] + blocks[i][bnum - 1] + popCount(bit[(i + 1) * bnum - 1]);
}
}
int rank(int pos, int kind) const {
if (kind == 0) {
return pos - rank1(pos);
} else {
return rank1(pos);
}
}
int rank1(int pos) const {
int cpos = pos / cw;
int bpos = pos % cw / bw;
int offset = pos % bw;
uint masked = (bit[cpos * bnum + bpos]) & ((1 << offset) - 1);
return chunk[cpos] + blocks[cpos][bpos] + popCount(masked);
}
int select(int num, int kind) const {
if (num == 0) return 0;
if (rank(length, kind) < num) return -1;
int ok = length, ng = 0;
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
if (rank(mid, kind) >= num) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
};
int bitVector::cw = 256;
int bitVector::bw = 32;
class WaveletMatrix {
public:
int length, data_size;
vector<bitVector> bvs;
vector<int> znum;
explicit WaveletMatrix(vector<long long> data, int _data_size) : length(data.size()), data_size(_data_size) {
bvs.assign(data_size, bitVector(length));
znum.assign(data_size, 0);
vector<long long> tmp[2];
for (int k = data_size - 1; k >= 0; --k) {
for (int i = 0; i < length; ++i) {
int b = (data[i] >> k) & 1;
bvs[k].set(i, b);
tmp[b].push_back(data[i]);
}
bvs[k].build();
znum[k] = tmp[0].size();
data.clear();
for (int b = 0; b < 2; ++b) {
copy(tmp[b].begin(), tmp[b].end(), back_inserter(data));
tmp[b].clear();
}
}
}
// 0-indexed
// 元のデータのdata[pos]を返す
long long access(int pos) {
long long ret = 0;
for (int k = data_size - 1; k >= 0; --k) {
long long b = bvs[k].access(pos);
ret += b << k;
pos = bvs[k].rank(pos + 1, b) - 1;
if (b == 1) pos += znum[k];
}
return ret;
}
// [0, pos)にあるkindの数
int rank(int pos, long long kind) {
int from = 0, to = pos;
for (int k = data_size - 1; k >= 0; --k) {
int b = (kind >> k) & 1;
from = bvs[k].rank(from, b);
to = bvs[k].rank(to, b);
if (b == 1) {
from += znum[k];
to += znum[k];
}
}
return to - from;
}
// [0, pos)にあるkind未満の数
int rank_less(int pos, long long kind) {
int from = 0, to = pos;
int ret = 0;
for (int k = data_size - 1; k >= 0; --k) {
int b = (kind >> k) & 1;
if (b == 1) {
ret += bvs[k].rank(to, 0) - bvs[k].rank(from, 0);
}
from = bvs[k].rank(from, b);
to = bvs[k].rank(to, b);
if (b == 1) {
from += znum[k];
to += znum[k];
}
}
return ret;
}
// [0, pos)にkindがnum個あるような最小のpos
// そもそもnum個なければ-1
int select(long long kind, int num) {
if (num == 0) return 0;
if (rank(length, kind) < num) return -1;
int ok = length, ng = 0;
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
if (rank(mid, kind) >= num) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
};
#include <iostream>
int main() {
int N;
cin >> N;
vector<long long> a(N), b(N);
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
for (int i = 0; i < N; ++i) {
cin >> b[i];
}
int ans = 0;
for (int k = 0; k < 29; ++k) {
int mask = (1LL << (k + 1)) - 1;
vector<long long> c(N);
for (int i = 0; i < N; ++i) {
c[i] = b[i] & mask;
}
WaveletMatrix wm(c, 32);
for (int i = 0; i < N; ++i) {
long long cnt = wm.rank_less(N, (1LL << k) * 4 - (a[i] & mask)) - wm.rank_less(N, (1LL << k) * 3 - (a[i] & mask)) + wm.rank_less(N, (1LL << k) * 2 - (a[i] & mask)) - wm.rank_less(N, max((1LL << k) * 1 - (a[i] & mask), 0LL));
ans ^= (cnt & 1) << k;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Two Sequences |
User |
Tiramister |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5941 Byte |
Status |
TLE |
Exec Time |
3156 ms |
Memory |
12432 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example_0, example_1, example_2, example_3 |
All |
N100000_0, N100000_1, N150000_0, N150000_1, N200000_0, N200000_1, N200000_ex_0, N200000_ex_1, example_0, example_1, example_2, example_3, rand_0, rand_1, smallrand_0, smallrand_1 |
Case Name |
Status |
Exec Time |
Memory |
N100000_0 |
TLE |
3156 ms |
6384 KB |
N100000_1 |
TLE |
3156 ms |
6380 KB |
N150000_0 |
TLE |
3156 ms |
10872 KB |
N150000_1 |
TLE |
3156 ms |
9904 KB |
N200000_0 |
TLE |
3156 ms |
12424 KB |
N200000_1 |
TLE |
3156 ms |
12424 KB |
N200000_ex_0 |
TLE |
3156 ms |
12432 KB |
N200000_ex_1 |
TLE |
3156 ms |
12432 KB |
example_0 |
AC |
2 ms |
256 KB |
example_1 |
AC |
2 ms |
256 KB |
example_2 |
AC |
2 ms |
256 KB |
example_3 |
AC |
2 ms |
256 KB |
rand_0 |
AC |
837 ms |
728 KB |
rand_1 |
AC |
1657 ms |
1120 KB |
smallrand_0 |
AC |
2 ms |
256 KB |
smallrand_1 |
AC |
2 ms |
256 KB |