Pagini recente » Cod sursa (job #1766533) | Cod sursa (job #2449633) | Cod sursa (job #1596672)
#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;
memset(fiu,NULL,sizeof(fiu));
}
};
trie *root = new trie();
void add_element (trie *nod, bool m[] , int siz , int ind)
{
if (siz<0)
{
if (ind>nod->bst) /// pentru determinarea secventei de lungime minima
nod->bst=ind;
return ;
}
if (nod->fiu[m[siz]]==NULL)
nod->fiu[m[siz]]=new trie();
add_element(nod->fiu[m[siz]],m,siz-1,ind);
}
int query (trie *nod, bool m[] , int siz)
{
if (siz<0)
return nod->bst;
if (nod->fiu[!m[siz]])
return query(nod->fiu[!m[siz]],m,siz-1);
else if (nod->fiu[m[siz]])
return query(nod->fiu[m[siz]],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)
{
summax=(dp[aux]^dp[i]);
bg=aux+1;
en=i;
}
add_element(root,mask,20,i);
}
g<<summax<<" "<<bg<<" "<<en;
return 0;
}