Cod sursa(job #2648042)

Utilizator adiaioanaAdia R. adiaioana Data 8 septembrie 2020 14:10:23
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>

using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");

struct Trie{
    Trie* zero;
    Trie* unu;
    int ind;
};

Trie *T=new Trie;

int N, st, dr, ans, v[100100];

inline void add(int I)
{
    Trie *p=T;
    for(int bit=21; bit>=0; --bit)
    {
        if(v[I]&(1<<bit))
        {
            if(p->unu==NULL)
                p->unu=new Trie;
            p=p->unu;
        }
        else {
            if(p->zero==NULL)
                p->zero=new Trie;
            p=p->zero;
        }
    }
    p->ind=I;
}

inline void query(int I)
{
    Trie *p=T;
    for(int bit=21; bit>=0; --bit)
    {
        if(v[I]&(1<<bit))
        {
            if(p->zero==NULL)
                p=p->unu;
            else p=p->zero;
        }
        else {
            if(p->unu==NULL)
                p=p->zero;
            else p=p->unu;
        }
    }

    int J=p->ind;
    int rez=v[I]^v[J];
    if(rez>ans)
    {
        ans=rez;
        st=J+1;
        dr=I;
    }
}
int main()
{
    int val;
    cin.sync_with_stdio(false);
    cin>>N;
    add(0);
    ans=-1;
    for(int i=1; i<=N; ++i)
    {
        cin>>val;
        v[i]=v[i-1]^val;
        query(i);
        add(i);
    }
    cout<<ans<<' '<<st<<' '<<dr<<'\n';
    return 0;
}