Pagini recente » Cod sursa (job #2849947) | Cod sursa (job #1796042) | Cod sursa (job #1815644) | Cod sursa (job #1147942) | Cod sursa (job #1942485)
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 2200000
#define MaxL 100005
#define INF 2140000000
using namespace std;
FILE*IN,*OUT;
struct Trie
{
int son0,son1;
}T[MaxN];
int N,Last[MaxN],DP[MaxL],Max=0,Start,End,Val,Size=0;
void New_Node(int x)
{
T[x].son0=T[x].son1=0;
}
void Update(int x)
{
int node=0;
for(int i=20;i>=0;i--)
{
if((x&(1<<i))>0)
{
if(T[node].son1==0)
{
New_Node(++Size);
T[node].son1=Size;
}
node=T[node].son1;
}
else
{
if(T[node].son0==0)
{
New_Node(++Size);
T[node].son0=Size;
}
node=T[node].son0;
}
}
}
int Query(int x)
{
int ans=0;
int node=0;
for(int i=20;i>=0;i--)
{
bool son=(x&(1<<i))>0;
if(!son)
{
if(T[node].son1!=0)
node=T[node].son1,ans+=1<<i;
else node=T[node].son0;
}
else
{
if(T[node].son0!=0)
node=T[node].son0;
else node=T[node].son1,ans+=1<<i;
}
}
return ans;
}
int main()
{
IN=fopen("xormax.in","r");
OUT=fopen("xormax.out","w");
fscanf(IN,"%d",&N);
for(int i=1;i<=N;i++)
{
fscanf(IN,"%d",&DP[i]);
DP[i]^=DP[i-1];
}
New_Node(0);
Update(0);
for(int i=1;i<=N;i++)
{
Val=Query(DP[i]);
if((DP[i]^Val)>Max)
Max=(DP[i]^Val),End=i,Start=Last[Val]+1;
Update(DP[i]);
Last[DP[i]]=i;
}
fprintf(OUT,"%d %d %d",Max,Start,End);
return 0;
}