Cod sursa(job #2820463)

Utilizator DordeDorde Matei Dorde Data 20 decembrie 2021 14:13:01
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int idx , pos;
struct Node{
    int p;
    Node *fii[2];
    Node(){
        p = -1;
        fii[0] = fii[1] = 0x0;
    }
};
class Trie{
private:
    Node *root;
    Node *add(Node *node , int bit , int x){
        if(node == 0x0)
            node = new Node();
        if(bit == -1){
            node->p = idx;
            return node;
        }
        int fiu = ((1 << bit) & x) != 0;
        node->fii[fiu] = add(node->fii[fiu] , bit - 1 , x);
        return node;
    }
    int query(Node *node , int bit , int x){
        if(bit == -1){
            pos = node->p;
            return 0;
        }
        int fiu = ((1 << bit) & x) != 0;
        fiu = !fiu;
        if(node->fii[fiu] == 0x0)
            fiu = !fiu;
        return ((1 << bit) * fiu) + query(node->fii[fiu] , bit - 1 , x);
    }
public:
    Trie(){
        root = 0x0;
    }
    void add(int nr){
        root = add(root , 20 , nr);
    }
    int query(int nr){
        return query(root , 20 , nr);
    }
}t;
int main()
{
    int n , xp = 0 , nr;
    fin >> n;
    t.add(xp);
    int l , r , ans = -1;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> nr;
        xp ^= nr;
        int best = t.query(xp);
        if((best ^ xp) > ans)
            tie(ans , l , r) = make_tuple((best ^ xp) , pos + 1 , i);
        idx = i;
        t.add(xp);
    }
    fout << ans << ' ' << l << ' ' << r << '\n';
    return 0;
}