Pagini recente » Cod sursa (job #836159) | Cod sursa (job #2172371) | Cod sursa (job #2099726) | Cod sursa (job #1815754) | Cod sursa (job #534240)
Cod sursa(job #534240)
#include<cstdio>
#include<algorithm>
using namespace std;
#define FOR(i, a, b) for(i = a ; i <= b ; i++)
const int NMAX = 100005;
const int BMAX = 23;
int N;
int a[NMAX];
int x[NMAX];
int c[BMAX], opus[BMAX];
int REZ;
int i;
int Y;
int v1, v2;
struct trie
{
trie *fiu[2];
int term;
trie()
{
fiu[0] = fiu[1] = 0;
term = 0;
}
};
trie *T = new trie;
void trans(int k)
{
fill(c, c + BMAX, 0);
int poz = BMAX - 1;
while(k) c[poz--] = k % 2, k /= 2;
}
void update(trie *nod, int poz)
{
if(poz == BMAX) {if(nod->term == 0)nod->term = i; return;}
if(nod->fiu[c[poz]] == 0) nod->fiu[c[poz]] = new trie;
update(nod->fiu[c[poz]], poz + 1);
}
void citi()
{
scanf("%d", &N);
FOR(i, 1, N)
{
scanf("%d", &a[i]);
x[i] = a[i] ^ x[i - 1];
trans(x[i]);
update(T, 0);
}
}
void cauta_opus(trie *nod, int poz)
{
if(nod->fiu[0] == 0 && nod->fiu[1] == 0) {Y = nod->term; return;}
if(nod->fiu[!c[poz]]) opus[poz] = !c[poz], cauta_opus(nod->fiu[!c[poz]], poz + 1);
else opus[poz] = c[poz], cauta_opus(nod->fiu[c[poz]], poz + 1);
}
int sau()
{
int sol = 0;
for(int j = 1 ; j < BMAX ; j++)
sol = 2*sol + (c[j]^opus[j]);
return sol;
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
citi();
FOR(i, 1, N)
{
trans(x[i]);
cauta_opus(T, 0);
int k = sau();
if(REZ < k)
{
REZ = k;
v1 = min(i, Y) + 1;
v2 = max(i, Y);
}
}
printf("%d %d %d\n", REZ, v1, v2);
return 0;
}