Cod sursa(job #3346592)
| Utilizator | Data | 14 martie 2026 14:15:49 | |
|---|---|---|---|
| Problema | Xor Max | Scor | 75 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 2.48 kb |
#include <bits/stdc++.h>
using namespace std;
long long sp[100555];
vector <int> v[1000555];
int b[45];
int p[25];
int vl[1000555];
int iv[1000555];
int main()
{
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n,x,e1,e2;
cin>>n;
int ix=0;
int mx=0;
p[0]=1;
for(int i=1;i<=21;++i)
{
p[i]=p[i-1]*2;
}
int nd=0;
for(int h=21;h>=0;--h)
{
int ex=-1;
for(auto a:v[nd])
{
if(vl[a]==b[h])
{
ex=a;
break;
}
}
if(ex==-1)
{
++ix;
vl[ix]=b[h];
v[nd].push_back(ix);
ex=ix;
}
nd=ex;
}
for(int i=1;i<=n;++i)
{
cin>>x;
sp[i]=(sp[i-1]^x);
int el=sp[i];
int in=0;
for(int h=0;h<=40;++h)
{
b[h]=0;
}
while(el)
{
if(el%2==1)
{
b[in]=1;
}
el/=2;
++in;
}
int nd=0;
long long int nr=0;
int s1=0;
for(int h=21;h>=0;--h)
{
int ex=-1;
for(auto a:v[nd])
{
if(vl[a]!=b[h])
{
ex=a;
break;
}
}
if(ex==-1)
{
ex=v[nd][0];
}
nd=ex;
if(i==n)
{
//cout<<b[h]<<" "<<h<<" "<<vl[nd]<<"\n";
}
if(vl[nd]!=b[h])
{
nr+=p[h];
}
s1=iv[nd];
}
if(nr>mx)
{
mx=nr;
e1=s1+1;
e2=i;
}
nd=0;
for(int h=21;h>=0;--h)
{
int ex=-1;
for(auto a:v[nd])
{
if(vl[a]==b[h])
{
ex=a;
break;
}
}
if(ex==-1)
{
++ix;
vl[ix]=b[h];
v[nd].push_back(ix);
ex=ix;
}
nd=ex;
iv[nd]=i;
}
}
cout<<mx<<" "<<e1<<" "<<e2;;
return 0;
}
