Pagini recente » Cod sursa (job #1071071) | Cod sursa (job #680503) | Cod sursa (job #3190170) | Cod sursa (job #1350046) | Cod sursa (job #838441)
Cod sursa(job #838441)
#include <cstdio>
#include <cstdlib>
#include <cassert>
#define MAXN 100000
#define DIGITS 22
int N;
int V[MAXN];
int X[MAXN + 1];
void actsol(int max, int start, int stop,
int& oldmax, int& oldstart, int& oldstop)
{
if(max > oldmax ||
(max == oldmax && stop < oldstop) ||
(max == oldmax && stop == oldstop && start > oldstart))
{
oldmax = max;
oldstart = start;
oldstop = stop;
}
}
void read()
{
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", V + i);
}
struct node
{
explicit node()
{
next[0] = next[1] = NULL;
ep = -1;
}
void add(int x, int bit_pos, int end_pos)
{
if(bit_pos == -1)
ep = end_pos;
else
{
int bit = (((1 << bit_pos) & x) != 0);
if(next[bit] == NULL)
next[bit] = new node();
next[bit]->add(x, bit_pos - 1, end_pos);
}
}
int get_best_ep(int current_xor, int bit_pos)
{
if(bit_pos == -1)
return ep;
else
{
int bit = (((1 << bit_pos) & current_xor) != 0);
if(next[1 - bit] != NULL) // this is the best choice
return next[1 - bit]->get_best_ep(current_xor, bit_pos - 1);
else
return next[bit]->get_best_ep(current_xor, bit_pos - 1);
}
}
node* next[2];
int ep;
};
void solve()
{
int a, b, c;
node *trie = new node();
int current_xor = 0;
a = -1;
trie->add(current_xor, DIGITS, 0);
X[0] = current_xor;
for(int i = 0; i < N; i++)
{
current_xor ^= V[i];
X[i + 1] = current_xor;
int best_pos = trie->get_best_ep(current_xor, DIGITS);
actsol(current_xor ^ X[best_pos], best_pos + 1, i + 1, a, b, c);
trie->add(current_xor, DIGITS, i + 1);
}
printf("%d %d %d\n", a, b, c);
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
read();
solve();
return 0;
}