Submission #1062137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062137		VMaksimoski008	XOR (IZhO12_xor)	C++17	100 / 100	1332 ms	43504 KiB

xor

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e6 + 5;

int id=1, trie[maxn][2];

void insert(int x) {
    int u = 0;
    for(int i=30; i>=0; i--) {
        bool b = x & (1 << i);
        if(!trie[u][b]) trie[u][b] = id++;
        u = trie[u][b];
    }
}

int XOR(int x) {
    int ans = 0, u = 0;
    for(int i=30; i>=0; i--) {
        bool b = x & (1 << i);
        if(trie[u][!b]) ans |= (1 << i), u = trie[u][!b];
        else u = trie[u][b];
    }
    return ans;
}

signed main() {
    int n, m;
    cin >> n >> m;

    vector<int> v(n+1), pref(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) pref[i] = v[i] ^ pref[i-1];

    int l=1, r=n, ans=1;
    while(l <= r) {
        int mid = (l + r) / 2;
        bool ok = 0;

        id = 1;
        memset(trie, 0, sizeof(trie));
        for(int i=mid; i<=n&&!ok; i++) {
            insert(pref[i-mid]);
            if(XOR(pref[i]) >= m) ok = 1;
        }

        if(ok) l = mid + 1, ans = mid;
        else r = mid - 1;
    }

    for(int i=ans; i<=n; i++) {
        if((pref[i] ^ pref[i-ans]) >= m) {
            cout << i-ans+1 << " " << ans << '\n';
            return 0;
        }
    }
    return 0;
}

• Subtask 1: 100 / 100