General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
151466387 Practice:
LMXZ
1658D2 - 60 C++17 (GCC 7-32) Accepted 264 ms 10344 KB 2022-03-31 07:45:51 2022-03-31 07:45:50
→ Source
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
//#undef LOCAL
#ifdef LOCAL
#define debug(x) cout << #x << "=" << (x) << endl
#define debugv(v)         \
    cout << #v << "=";    \
    for (auto _ : v)      \
        cout << _ << " "; \
    cout << endl;
#else
#define assert(x)
#define debug(x)
#define debugv(v)
#endif

using namespace std;

const int N = 1 << 17;
vector sum(19, vector<int>(N));

int ssum(int b, int l, int r) {
    return sum[b][r] - (l ? sum[b][l - 1] : 0);
}

void testc() {
    int l, r;
    cin >> l >> r;
    int n = r - l + 1;
    vector a(n, 0);
    for (auto& i : a)
        cin >> i;
    int h = 0, ans = 0, flg = -1;
    for (int i = 18, j = (1 << 18); i >= 0; i--, j >>= 1) {
        int c1 = 0;
        for (int x : a)
            if (x & j)
                c1++;
        if (c1 == 0 || c1 == n) {
            if (c1 != ssum(i, l, r))
                ans ^= j;
            if (ssum(i, l, r) == n)
                h ^= j;
        } else {
            h ^= j;
            flg = j;
            if (c1 != ssum(i, l, r))
                ans ^= j;
            break;
        }
    }
    if (flg == -1)
        return void(cout << ans);
    debug(h);
    vector s(2, vector(19, 0));
    for (int i = 0, j = 1; j < flg; i++, j <<= 1) {
        for (int x : a) {
            if (x & j)
                s[((x ^ ans) & flg) ? 1 : 0][i]++;
        }
    }
    for (int i = 0; (1 << i) < flg; i++) {
        if (s[0][i] != ssum(i, l, h - 1) || s[1][i] != ssum(i, h, r))
            ans ^= 1 << i;
    }
    cout << ans;
#ifdef LOCAL
    cout << endl;
    map<int, int> mp;
    for (int i : a)
        mp[i ^ ans]++;
    for (auto [k, v] : mp) {
        assert(l <= k && k <= r && v == 1);
    }
#endif
}

void init() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif  //! LOCAL
    for (int i = 0; i < N; i++) {
        for (int j = 0, k = 1; k <= i; j++, k <<= 1)
            if (i & k) {
                sum[j][i]++;
            }
    }
    for (auto& v : sum) {
        int n = v.size();
        for (int i = 1; i < n; i++)
            v[i] += v[i - 1];
    }
}

int main() {
    init();
    int t = 1;
    cin >> t;
    while (t--) {
        testc();
        if (t)
            cout << endl;
    }
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details