5429 2023. 05. 23 16:08:31 111 Xorzótábla cpp14 Időlimit túllépés 35/100 2.076s 66400 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define BSEARCH(v, x) (distance((v).begin(), lower_bound((v).begin(), (v).end(), (x))))

#define BIT(x, i) ((x) >> (i) & 1ll)
#define LOPT(i) (~0ll ^ ~0ll << (i))

main() {
int AC, BC;
cin >> AC >> BC;
vector<int> A(AC), B(BC);
for (int i = 0; i < AC; i++) {
cin >> A[i];
}
for (int i = 0; i < BC; i++) {
cin >> B[i];
}
vector<vector<int>> v(34);
vector<vector<int>> w(34);
int x = 0;
for (int i = 0; i < 34; i++) {
for (int j = 0; j < AC; j++) {
if (BIT(A[j], i)) {
v[i].push_back(A[j] & LOPT(i));
}
else {
w[i].push_back(A[j] & LOPT(i));
}
}
sort(v[i].begin(), v[i].end());
sort(w[i].begin(), w[i].end());
}
for (int i = 0; i < BC; i++) {
for (int j = 0; j < 34; j++) {
int c = 0;
if (BIT(B[i], j)) {
c += w[j].size();
c += v[j].size() - BSEARCH(v[j], (1ll << j) - (B[i] & LOPT(j)));
c -= w[j].size() - BSEARCH(w[j], (1ll << j) - (B[i] & LOPT(j)));
}
else {
c += v[j].size();
c += w[j].size() - BSEARCH(w[j], (1ll << j) - (B[i] & LOPT(j)));
c -= v[j].size() - BSEARCH(v[j], (1ll << j) - (B[i] & LOPT(j)));
}
x ^= c % 2 << j;
}
}
cout << x << endl;
return 0;
}

Részfeladat Összpont Teszt Verdikt Idő Memória
15 Időlimit túllépés 2.076s 34000 KiB
16 Időlimit túllépés 2.028s 65188 KiB
17 Időlimit túllépés 2.028s 65188 KiB