Pagini recente » Diferente pentru monthly-2014/runda-9/solutii intre reviziile 16 si 12 | Cod sursa (job #577814) | Cod sursa (job #2021100) | Cod sursa (job #1472956) | Cod sursa (job #2006840)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie{int x0,x1,val;}init;
vector <trie>v;
int n,X[100005],lg,q,pow[25],z,p1,p2,I,mx,aux,Y;
int last[3000000];
bool x[25],y[25];
void Update(int P,int poz,int vl)
{//fout<<poz<<" "<<P<<" ";
if(poz==22)
v[P].val=vl;
else {if(x[poz]==0&&v[P].x0==0){n++;v.push_back(init);v[P].x0=n;}
else if(x[poz]==1&&v[P].x1==0){n++;v.push_back(init);v[P].x1=n;}
if(x[poz]==0){//fout<<"0\n";
Update(v[P].x0,poz+1,vl);
}
else {//fout<<"1\n";
Update(v[P].x1,poz+1,vl);
}
}
}
void Querry(int P,int poz)
{int i;//fout<<"AAAAA";
if(v[P].val&&poz==22)
{if(z>mx){mx=z;p1=last[X[v[P].val+1]];p2=I;}
}
else{if(x[poz]==1)
{if(v[P].x0){z+=pow[poz];Querry(v[P].x0,poz+1);}
else Querry(v[P].x1,poz+1);
}
else
{if(v[P].x1){z+=pow[poz];Querry(v[P].x1,poz+1);}
else Querry(v[P].x0,poz+1);
}
}
}
void Afisare(int P)
{fout<<v[P].val<<" "<<P<<"\n";
if(v[P].x0!=0)Afisare(v[P].x0);
if(v[P].x1!=0)Afisare(v[P].x1);
}
int main()
{int i,j,N;
init.val=0;
init.x0=0;
init.x1=0;
v.push_back(init);
fin>>N;
pow[1]=1;
for(i=2;i<=21;i++)
pow[i]=pow[i-1]*2;
for(i=1;i<=10;i++)
{aux=pow[i];
pow[i]=pow[22-i];
pow[22-i]=aux;//fout<<X<<" "<<Y<<"\n";
}
for(i=1;i<=N;i++)
{fin>>X[i];
X[i]=X[i]^Y;
last[X[i]]=i;
// fout<<X<<" "<<Y<<"\n";
lg=0;
for(j=1;j<=21;j++)
x[j]=0;
Y=X[i];
while(X[i])
{lg++;
x[lg]=X[i]%2;
X[i]/=2;
}
for(j=1;j<=10;j++)
{aux=x[j];
x[j]=x[22-j];
x[22-j]=aux;
}
I=i;
Update(0,1,i);
z=0;
Querry(0,1);
//fout<<z<<" \n";
// for(j=1;j<=21;j++)
// y[j]=x[j];
}
//Afisare(0);
fout<<mx<<" "<<p1<<" "<<p2;
}