QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227131#6795. Everyone Loves Playing Gamesjzh#AC ✓32ms3804kbC++201.6kb2023-10-26 22:55:412023-10-26 22:55:42

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 22:55:42]
  • 评测
  • 测评结果:AC
  • 用时:32ms
  • 内存:3804kb
  • [2023-10-26 22:55:41]
  • 提交

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