Pagini recente » Cod sursa (job #700491) | Cod sursa (job #1779108) | Cod sursa (job #1024348) | Cod sursa (job #307241) | Cod sursa (job #2888177)
//Ilie Dmitru
#include<fstream>
#include<cstdio>
typedef long long int ll;
const int NMAX=100005;
const ll MOD=194767;
const int maxBIT=1<<20;
std::ifstream f("xormax.in");
std::ofstream g("xormax.out");
struct trie
{
trie* next[2];
int pos;
};
void init(trie*& t)
{
t=new trie;
t->next[0]=t->next[1]=0;
t->pos=-2;
}
void push(trie*& t, int x, int pos, int bit=maxBIT)
{
int val=!!(x&bit);
if(!t)
init(t);
if(bit)
push(t->next[val], x, pos, bit>>1);
else if(t->pos==-2)
t->pos=pos;
}
trie* t;
void clear(trie*& t)
{
if(t)
{
clear(t->next[0]);
clear(t->next[1]);
delete t;
}
}
int findMax(trie* t, int x, int& startPos, int bit=maxBIT)
{
int val=!(x&bit), res=0;
if(t->next[val])
res=bit|findMax(t->next[val], x, startPos, bit>>1);
else if(t->next[!val])
res=findMax(t->next[!val], x, startPos, bit>>1);
else
res=0, startPos=t->pos;
return res;
}
char s[NMAX*8];
int v[NMAX];
int main()
{
int i, N, x=0, r, ans=0, pos, bestStart=-1, bestEnd=-1;
f>>N;
f.get();
f.getline(s, NMAX*8);
for(i=pos=0;s[i];++i)
{
if(s[i]!=' ')
x=x*10+s[i]-'0';
else
v[pos++]=x, x=0;
}
v[pos]=x;
push(t, 0, -1);
x=0;
for(i=0;i<N;++i)
{
x^=v[i];
r=findMax(t, x, pos);
push(t, x, i);
if(r>ans)
{
ans=r;
bestStart=pos;
bestEnd=i;
}
}
g<<ans<<' '<<bestStart+2<<' '<<bestEnd+1;
clear(t);
f.close();
g.close();
return 0;
}