Submission #1325702

#TimeUsernameProblemLanguageResultExecution timeMemory
1325702muzanXOR (IZhO12_xor)C++20
100 / 100
109 ms34280 KiB
#include <bits/stdc++.h>
using namespace std;

const int L = 30;
struct Trie {
    struct node : array<int, 2> {
        int cnt{};
        int mx = -1;
    };
    vector<node> tr;
    Trie() : tr(2) { }

    int nxt(int x, int c) {
        if(tr[x][c]) return tr[x][c];
        tr.emplace_back();
        return tr[x][c] = int(tr.size()) - 1;
    }

    void add(int v, int j) {
        int x = 1;
        for(int i = L - 1; i >= 0; i--) {
            tr[x].cnt++;
            tr[x].mx = max(tr[x].mx, j);
            x = nxt(x, v >> i & 1);
        }
        tr[x].cnt++;
        tr[x].mx = max(tr[x].mx, j);
    }

    int query(int v, int k) {
        int x = 1;
        for(int i = L - 1; i >= 0; i--) {
            int xor0 = tr[x][v >> i & 1];
            int xor1 = tr[x][v >> i & 1 ^ 1];

            if(!(k >> i & 1)) {
                if(tr[xor0].mx > tr[xor1].mx) x = xor0;
                else x = xor1;
            }
            else {
                x = xor1;
            }
        }
        return tr[x].mx;
    }
};

void TC() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int &i : a) cin >> i;

    int bestI = 0, bestK = 0;
    int suf = 0;
    Trie tr;
    tr.add(suf, n);
    for(int i = n - 1; i >= 0; i--) {
        suf ^= a[i];
        tr.add(suf, i);
        int j = tr.query(suf, k);
        if(j - i >= bestK) bestK = j - i, bestI = i;
    }
    cout << bestI + 1 << ' ' << bestK << '\n';
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int tc = 1;
//    cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        TC();
    }
//    cerr << clock() / 1000.0 << " Secs";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...