Cod sursa(job #1350019)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 20 februarie 2015 16:55:43
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#define DIM 100011
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,t;
int v[DIM],p[1<<21];

struct trie{
    int nr;
    trie *next[2];
    trie(){
        nr=0;
        next[0]=next[1]=0;
    }
};
trie *root;

void update(trie *r,int x,int nr,int poz){
    if(nr){
        int y=x&(1<<nr),z=0;
        if(y) z=1;
        if(r->next[z]==0)
            r->next[z]=new trie;
        update(r->next[z],x^y,nr-1,poz);
    }
    else
        r->nr=poz;
}

int query(trie *r,int x,int nr){
    if(nr){
        int y=x&(1<<nr),z=0;
        if(y) z=0;
        if(r->next[1-z])
            return query(r->next[1-z],x^y,nr-1);
        else
            return query(r->next[z],x^y,nr-1);
    }
    else
        return r->nr;
}

int main(void){
    register int i,j,x,s,poz;
    int sol=0,st,dr;

    root=new trie;
    p[0]=p[1]=1;
    for(i=2;i<(1<<21);i++) p[i]=p[i/2]+1;

    f>>n;
    for(i=1;i<=n;i++){
        f>>v[i];
        v[i]^=v[i-1];
        t=max(p[v[i]],t);
    }
    update(root,0,--t,0);
    for(i=1;i<=n;i++){
        poz=query(root,v[i],t);
        s=v[poz]^v[i];
        if(s<v[i] && sol<v[i])
            sol=v[i],st=dr=i;
        if(s>sol)
            sol=s,st=poz+1,dr=i;
        update(root,v[i],t,i);
    }

    g<<sol<<" "<<st<<" "<<dr;
    f.close();
    g.close();
    return 0;
}