Cod sursa(job #2623601)

Utilizator bem.andreiIceman bem.andrei Data 3 iunie 2020 14:49:42
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("xormax.in");
ofstream w("xormax.out");
int v[100002], maxim=-1000000000, st, dr, n;
class trie
{
    int fin;
    trie *t[2];
public:
    trie()
    {
        t[0]=nullptr;
        t[1]=nullptr;
    }
    void push(int a, int b, int ans=20)
    {
        if(ans<0){
            fin=b;
            return;
        }
        int val=(a&(1<<ans))>0;
        if(t[val]==nullptr){
            t[val]=new trie;
        }
        t[val]->push(a, b, ans-1);
    }
    int querry(int a, int ans=20){
        if(ans<0){
            return fin;
        }
        int val=(a&(1<<ans))==0;
        if(t[val]==nullptr){
            return t[!val]->querry(a, ans-1);
        }
        return t[val]->querry(a, ans-1);
    }
};
trie *root= new trie;
int main()
{
    r>>n;
    root->push(0,0);
    for(int i=1; i<=n; i++)
    {
        r>>v[i];
        v[i]^=v[i-1];
        int a=root->querry(v[i]);
        if(v[a]^v[i]>maxim){
            maxim=(v[a]^v[i]);
            st=a+1;
            dr=i;
        }
        root->push(v[i], i);
    }
    w<<maxim<<" "<<st<<" "<<dr<<"\n";
    return 0;
}