Cod sursa(job #2143405)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 25 februarie 2018 21:46:45
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<vector>
#include<cctype>
using namespace std;
#define NIL 0
struct trie{
int num;
trie *fii[2];
};
trie* getnod(){
trie *nod=new trie;
nod->fii[0]=NIL;
nod->fii[1]=NIL;
return nod;}
trie *root=getnod();
int num,start;
int add(int val,int poz){
trie *aux=root;
int i;
for(i=20;i>=0;i--){
if (aux->fii[((val&(1<<i))>0)]==NIL)
aux->fii[((val&(1<<i))>0)]=getnod();
aux=aux->fii[((val&(1<<i))>0)];}
aux->num=poz;}
int calc(int val){
trie *aux=root;
int i;
num=0;
for(i=20;i>=0;i--)
if (val&(1<<i)){
if (aux->fii[0]==NIL)
aux=aux->fii[1];
else
aux=aux->fii[0],num=num+(1<<i);}
else{
if (aux->fii[1]==NIL)
aux=aux->fii[0];
else
aux=aux->fii[1],num=num+(1<<i);}
start=aux->num;}
int main(){
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
int n,i,x,xori=0,maxim=-1,st,dr;
scanf("%d",&n);
add(0,0);
for(i=1;i<=n;i++){
scanf("%d",&x);
xori=xori^x;
calc(xori);
if (num>maxim)
maxim=num,st=start+1,dr=i;
add(xori,i);}
printf("%d %d %d\n",maxim,st,dr);
return 0;}