Pagini recente » Cod sursa (job #17512) | Cod sursa (job #2282632)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int NMAX = 100005;
int v[NMAX];
int p[25],s[25],ma=0,x,y,n;
struct trie{
trie *bit[2];
int numar;
trie()
{
numar = 0;
bit[1] = bit[0] = NULL;
}
};
trie *radacina = new trie;
void adauga(trie *&nod,int i,int dr)
{
if(i == 22)
{
nod->numar = dr;
return;
}
if(nod->bit[s[i]] == NULL)
nod->bit[s[i]] = new trie;
adauga(nod->bit[s[i]],i+1,dr);
}
void putInS(int x)
{
memset(s,0,sizeof(s));
int k = -1;
while(x)
{
s[++k] = (x&1);
x >>= 1;
}
for (int i = 0; i <= 10; i++)
swap (s[i],s[21-i]);
}
int cauta(trie *&nod,int i)
{
if(i == 22)
{
y = nod->numar;
return 0;
}
if(nod->bit[1-s[i]]!=NULL)
return p[(21-i)]+cauta(nod->bit[1-s[i]],i+1);
else
return cauta(nod->bit[s[i]],i+1);
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
scanf("%d",&v[i]);
for(int i = 1 ; i <= n ; i++)
v[i] = v[i] ^ v[i-1];
p[0] = 1;
for(int i = 1 ; i <= 22 ; i++)
p[i] = (p[i-1]<<1);
ma = 0;
int num;
putInS(0);
adauga(radacina,0,0);
int stm,drm;
stm = drm = 1;
for(int i = 1 ; i <= n ; i++)
{
putInS(v[i]);
num = cauta(radacina,0);
if(num > ma)
{
ma = num;
stm = y;
drm = i;
}
adauga(radacina,0,i);
}
printf("%d %d %d\n",ma,stm+1,drm);
return 0;
}