Cod sursa(job #2316996)

Utilizator bogdi1bogdan bancuta bogdi1 Data 12 ianuarie 2019 17:28:39
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>

using namespace std;
struct Trie
{
    int ind;
    Trie *fii[2];
    Trie(){
        ind=0;
        fii[0]=NULL;
        fii[1]=NULL;
    }
};
Trie *root=new Trie;
int put2[25];
int xors[100005];
int rez,last;
void insert(Trie *nod, int val, int ind)
{
    int i;
    for(i=20; i>=0; i--){
        if(nod->fii[val/put2[i]]==NULL)
            nod->fii[val/put2[i]]=new Trie;
        nod->ind=ind;
        nod=nod->fii[val/put2[i]];
        val%=put2[i];
    }
}
int find(Trie *nod, int val)
{
    int i;
    for(i=20; i>=0; i--){
        last=nod->ind;
        if(nod->fii[1-val/put2[i]]==NULL)
            nod=nod->fii[val/put2[i]];
        else{
            rez+=put2[i];
            nod=nod->fii[1-val/put2[i]];
        }
        val=val%put2[i];
    }
    return last;
}
int main()
{   freopen("xormax.in", "r",stdin);
    freopen("xormax.out", "w",stdout);
    int n,i,x,ind,maxx=0,st,dr;
    scanf("%d", &n);
    put2[0]=1;
    for(i=1; i<=21; i++)
        put2[i]=2*put2[i-1];
    for(i=1; i<=n; i++){
        scanf("%d", &x);
        xors[i]=xors[i-1]^x;
    }
    for(i=1; i<=n; i++){
        insert(root, xors[i-1], i-1);
        rez=0;
        ind=find(root, xors[i]);
        if(rez>maxx){
            maxx=rez;
            st=ind+1;
            dr=i;
        }
    }
    printf("%d %d %d", maxx, st, dr);
    return 0;
}