Pagini recente » Cod sursa (job #2452882) | Cod sursa (job #2906712) | Cod sursa (job #1715349) | Cod sursa (job #2786373) | Cod sursa (job #1889212)
#include <cstdio>
#define BIT(x) (1<<(x))
#define bmax 20
using namespace std;
struct Trie
{
Trie* f[2];
int ind;
Trie()
{
f[0] = f[1] = NULL;
}
} r;
int val;
int rval, pval;
int best, ibest, sbest;
void update(Trie* t, int pos = bmax)
{
t->ind = pval;
if(pos < 0) return;
if(val & BIT(pos))
{
if(t->f[1] == NULL)
t->f[1] = new Trie();
update(t->f[1], pos - 1);
}
else
{
if(t->f[0] == NULL)
t->f[0] = new Trie();
update(t->f[0], pos - 1);
}
}
void query(Trie* t, int pos = bmax)
{
if(pos < 0)
{
pval = t->ind;
return;
}
if(val & BIT(pos))
{
if(t->f[0] != NULL)
{
rval |= BIT(pos);
query(t->f[0], pos - 1);
}
else
{
query(t->f[1], pos - 1);
}
}
else
{
if(t->f[1] != NULL)
{
rval |= BIT(pos);
query(t->f[1], pos - 1);
}
else
{
query(t->f[0], pos - 1);
}
}
}
int main()
{
int n;
int sum = 0, x;
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
val = 0;
pval = 0;
ibest = 1;
sbest = 1;
update(&r);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &x);
sum ^= x;
val = sum;
rval = 0;
query(&r);
if(rval > best)
{
best = rval;
ibest = pval + 1;
sbest = i;
}
val = sum;
pval = i;
update(&r);
}
printf("%d %d %d", best, ibest, sbest);
return 0;
}