Cod sursa(job #2823967)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 30 decembrie 2021 13:11:59
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;
#ifdef INFOARENA
#define cin fin
#define cout fout
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#endif // INFOARENA
const int l = 20;
class Trie {
public:
    struct node {
        node* to[2];
        int ind;
        node (int _ind) : ind(_ind), to({NULL, NULL}) {}
        node* go_to(bool d) { if(to[d]) { to[d] -> ind = ind; return to[d]; } return to[d] = new node(ind); }
    };
    int k = 0;
    node* root = new node(0);
    Trie() { node* curr = root; for(int i = l; i >= 0; i--) curr = curr -> go_to(0); }
    void add(int x) {
        node* curr = root; curr -> ind = ++k;
        for(int i = l; i >= 0; i--)
            curr = curr -> go_to(x & (1 << i));
    }
    int query(int x, node* t, int depth) {
        if(depth == 0) return t -> ind;
        if(((x & (1 << depth - 1)) && t -> to[0]) || !t -> to[1]) return query(x, t -> to[0], depth - 1);
        else return query(x, t -> to[1], depth - 1);
    }
    int query(int x) { return query(x, root, l + 1); }
};
const int N = 1e5;
int ps[N + 5];

int main()
{
    Trie T;
    int px = 0, n, x, res = -1, ql, l = 0, r = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        T.add(ps[i] = (px ^= x));
        int q = px ^ ps[ql = T.query(px)];
        if(res < q) res = q, l = ql + 1, r = i;
    }
    cout << res << " " << l << " " << r << "\n";
    return 0;
}