Pagini recente » Cod sursa (job #2450031) | Cod sursa (job #2116574) | Cod sursa (job #284675) | Cod sursa (job #170711) | Cod sursa (job #1608691)
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int nmax=100005;
int n,dp[nmax],x,i,summax,bg,en,j;
bool mask[25];
struct trie
{
int bst;
trie *fiu[2];
trie ()
{
bst=-1;
fiu[0]=fiu[1]=NULL;
}
};
trie *root = new trie();
void add_element (trie *nod, bool m[] , int siz , int ind)
{
if (siz<0)
{
if (ind>nod->bst)
nod->bst=ind;
return;
}
if (nod->fiu[m[i]]==NULL)
nod->fiu[m[i]]=new trie();
add_element(nod->fiu[m[i]],m,siz-1,ind);
}
int query (trie *nod, bool m[] , int siz)
{
if (siz<0)
return nod->bst;
if (nod->fiu[!m[i]])
return query(nod->fiu[!m[i]],m,siz-1);
else if (nod->fiu[m[i]])
return query(nod->fiu[m[i]],m,siz-1);
return -1;
}
int main()
{
int aux;
f>>n;
add_element(root,mask,20,0);
for (i=1;i<=n;i++)
{
f>>x;
dp[i]=(x ^ dp[i-1]);
for (j=0;j<=20;j++)
mask[j]=(dp[i]&(1<<j));
aux=query(root,mask,20);
if ((dp[aux]^dp[i])>summax)
{
bg=aux+1;
en=i;
summax=(dp[aux]^dp[i]);
}
add_element(root,mask,20,i);
}
g<<summax<<" "<<bg<<" "<<en;
return 0;
}