QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227131 | #6795. Everyone Loves Playing Games | jzh# | AC ✓ | 32ms | 3804kb | C++20 | 1.6kb | 2023-10-26 22:55:41 | 2023-10-26 22:55:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Base {
ll d[70];
Base() {
for (int i=0; i<=60; i++) d[i] = 0;
}
ll& operator[](int i) {return d[i];}
bool add(ll x) {
for (int i=60; i>=0; i--) if (x&(1ll<<i)) {
if (d[i]) {
x ^= d[i];
}
else {
d[i] = x;
return true;
}
}
return false;
}
};
void solve()
{
int n, m;
scanf("%d%d", &n, &m);
vector<ll> orig_a(n);
vector<ll> orig_b(m);
Base base_a, base_b;
ll X = 0;
for (ll i=0, x, y; i<n; i++) {
scanf("%lld%lld", &x, &y);
orig_a[i] = x^y;
X ^= x;
base_a.add(orig_a[i]);
}
for (ll i=0, x, y; i<m; i++) {
scanf("%lld%lld", &x, &y);
orig_b[i] = x^y;
X ^= x;
base_b.add(orig_b[i]);
}
for (int i=60; i>=0; i--) {
if (base_a[i]==0 && base_b[i]==0) {
continue;
}
else if (base_b[i]==0) {
if ((X&(1ll<<i)) == 0) {
X ^= base_a[i];
}
}
else if (base_a[i]==0) {
if (X&(1ll<<i)) {
X ^= base_b[i];
}
}
else {
if (X&(1ll<<i)) {
X ^= base_a[i];
}
base_a.add(base_a[i]^base_b[i]);
}
}
printf("%lld\n", X);
}
int main()
{
int ttt;
scanf("%d", &ttt);
while (ttt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
2 1 1 6 3 4 1 2 2 1 3 4 6 5 4 2 2
output:
2 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 32ms
memory: 3804kb
input:
15 10000 19 393592642880030158 136857754781138651 64253273480262588 14313422237514072 307460297920437500 243820607396725 21817935197991240 483662625803120946 101295580681553439 176530315178675718 299210522568785323 76213955574929634 71280408782239858 46474979272278520 355918902735266055 227582800425...
output:
2199023255551 5910974510923775 17179869183 1008806316530991103 855638015 2424831 163208757247 12884901887 12582911 17179869183 402595213 2199023255549 10485759 983039 2265548478697
result:
ok 15 lines