Cod sursa(job #2740285)
Utilizator | Andrei Boaca hhhhhhh | Data | 12 aprilie 2021 14:17:12 |
---|---|---|---|
Problema | Xor Max | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.87 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
typedef long long ll;
int n,s[200005],l,r,f[3000005][21];
ll ans;
const int inf=1e9;
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin>>n;
for(int i=1;i<=n;i++)
{
int x;
fin>>x;
s[i]=(s[i-1]^x);
}
/*if(n==1)
{
fout<<s[1]<<" 1 1";
return 0;
}*/
for(int i=1;i<=3*1e6;i++)
memset(f[i],-1,sizeof(f[i]));
//fout<<query(1,0,(1<<21),3,120)<<'\n';
for(int i=1;i<=n;i++)
{
int nr=0;
for(int bit=20;bit>=0;bit--)
{
if((s[i]>>bit)&1)
{
int bestpoz=f[nr][bit];
if(bestpoz!=-1)
{
int val=(s[i]^s[bestpoz]);
if(val>ans)
{
ans=val;
l=bestpoz+1;
r=i;
}
}
else
nr+=(1<<bit);
}
else
{
int bestpoz=f[nr+(1<<bit)][bit];
if(bestpoz!=-1)
{
int val=(s[i]^s[bestpoz]);
if(val>ans)
{
ans=val;
l=bestpoz+1;
r=i;
}
nr+=(1<<bit);
}
}
}
int x=0;
for(int bit=20;bit>=0;bit--)
{
if((s[i]>>bit)&1)
x+=(1<<bit);
f[x][bit]=i;
}
}
if(l==0&&r==0)
{
fout<<s[1]<<" "<<1<<" "<<1;
return 0;
}
fout<<ans<<" "<<l<<" "<<r;
return 0;
}