Cod sursa(job #3166263)

Utilizator StefannnnnStefan Stefannnnn Data 8 noiembrie 2023 00:50:39
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

struct trie {
    trie *f[2];
    int val, ind;
    trie() {
        f[1] = f[0] = NULL;
        val = ind = 0;
    }
};

void update(trie *&root, int val, int ind) {
    trie *curr = root;
    for(int i = 20; i >= 0; i --) {
        int bit = ((val >> i) & 1);
        if(curr->f[bit] == NULL) {
            curr->f[bit] = new trie;
        }
        curr = curr->f[bit];
    }
    curr->val = val;
    curr->ind = ind;
}

pair<int, int> query(trie *&root, int val) {
    trie *curr = root;
    for(int i = 20; i >= 0; i--) {
        int bit = ((val >> i) & 1);
        if(curr->f[1 - bit] == NULL) {
            curr = curr->f[bit];
        } else {
            curr = curr->f[1 - bit];
        }
    }
    return {curr->val, curr->ind};
}

int main() {
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    trie *root = new trie;
    int n, tot = 0, l, r, maxx = -1;
    cin >> n;
    update(root, 0, 0);
    for(int i = 1; i <= n; i ++) {
        int a;
        cin >> a;
        tot ^= a;
        pair<int, int> acm = query(root, tot);
        if(((acm.first) ^ tot) > maxx) {
            maxx = ((acm.first) ^ tot);
            l = acm.second + 1;
            r = i;
        }
        update(root, tot, i);
    }
    cout << maxx << " " << l << " " << r;
}