Submission #1062126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062126		VMaksimoski008	XOR (IZhO12_xor)	C++17	0 / 100	473 ms	262144 KiB

xor

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

struct Node {
    map<int, Node*> mp;
    Node() {}
};

struct Trie {
    Node *root;

    Trie() { root = new Node(); }
    ~Trie() { delete root; }

    void insert(int &x) {
        Node *curr = root;
        for(int i=30; i>=0; i--) {
            bool b = x & (1 << i);
            if(!curr->mp.count(b)) curr->mp[b] = new Node();
            curr = curr->mp[b];
        }
    }

    int XOR(int &x) {
        int ans = 0;
        Node *curr = root;
        for(int i=30; i>=0; i--) {
            bool b = x & (1 << i);
            if(curr->mp.count(!b)) {
                ans |= (1 << i);
                curr = curr->mp[!b];
            } else {
                curr = curr->mp[b];
            }
        }
        return ans;
    }

    void reset() { root = new Node(); }
};

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];

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

        trie.reset();
        for(int i=mid; i<=n&&!ok; i++) {
            trie.insert(pref[i-mid]);
            if(trie.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: 0 / 100