5430 2023. 05. 23 16:39:27 111 Xorzótábla cpp14 Elfogadva 100/100 1.934s 34356 KiB
#include <bits/stdc++.h>
using namespace std;

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

// az stl-re semmit se lehet bizni...

int cmp(const void* a, const void* b) {
if (*(int*)a < *(int*)b) {
return -1;
}
else if (*(int*)a > *(int*)b) {
return 1;
}
else {
return 0;
}
}

int bs(const vector<int>& v, int x) {
int l = 0, h = v.size();
while (l != h) {
int m = (l + h) / 2;
if (v[m] >= x) {
h = m;
}
else {
l = m + 1;
}
}
return h;
}

int 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(32);
vector<vector<int>> w(32);
int x = 0;
for (int i = 0; i < 32; 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));
}
}
qsort(v[i].data(), v[i].size(), sizeof(int), cmp);
qsort(w[i].data(), w[i].size(), sizeof(int), cmp);
}
for (int i = 0; i < BC; i++) {
for (int j = 0; j < 32; j++) {
int c = 0;
int y = (1 << j) - (B[i] & LOPT(j));
if (BIT(B[i], j)) {
c += w[j].size();
c += v[j].size() - bs(v[j], y);
c -= w[j].size() - bs(w[j], y);
}
else {
c += v[j].size();
c += w[j].size() - bs(w[j], y);
c -= v[j].size() - bs(v[j], y);
}
x ^= c % 2 << j;
}
}
cout << x << endl;
return 0;
}

Részfeladat Összpont Teszt Verdikt Idő Memória