Cod sursa(job #2143389)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 25 februarie 2018 21:25:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<cstdio>
#include<vector>
#include<cctype>
using namespace std;
#define NIL 0
char buff[1000005];
const int buffs=1000000;
int poz=0;
int read(){
char ch;
int nr=0;
do{
ch=buff[poz++];
}while(!isdigit(ch));
do{
nr=nr*10+ch-'0';
ch=buff[poz++];
}while(isdigit(ch));
return nr;}
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;
fread(buff,1,buffs,stdin);
n=read();
add(0,0);
for(i=1;i<=n;i++){
x=read();
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;}