Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/anabat | Cod sursa (job #2443940) | Cod sursa (job #132092)
Cod sursa(job #132092)
#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;
#define NMAX 100001
#define pb push_back
int N, M;
int V[NMAX], X[NMAX];
int trie[NMAX*21][2];
void Update_Trie (int x, int poz)
{
int i, bit, nod = 0;
for (i = 20; i >= 0; -- i)
{
bit = (x & (1 << i)) != 0;
if (!trie[nod][bit])
trie[nod][bit] = ++ M;
nod = trie[nod][bit];
}
trie[nod][0] = -poz;
}
void read ()
{
scanf ("%d\n", &N);
int i;
for (i = 1; i <= N; ++ i)
{
scanf ("%d ", V + i);
X[i] = X[i-1] ^ V[i];
}
}
void solve ()
{
int i, j, st, dr, Max = 0, nod, bit, temp;
for (i = N; i >= 0; -- i)
Update_Trie (X[i], i);
for (i = 0; i <= N; ++ i)
{
nod = temp = 0;
for (j = 20; j >= 0; -- j)
{
bit = (X[i] & (1 << j)) != 0;
bit ^= 1;
if (trie[nod][bit] > 0)
{
nod = trie[nod][bit];
temp += (1 << j);
}
else if (!trie[nod][bit])
nod = trie[nod][1-bit];
}
if (-trie[nod][0] + 1 > i)
continue;
if (Max < temp)
{
Max = temp;
st = -trie[nod][0] + 1;
dr = i;
}
else if (Max == temp)
if (st > -trie[nod][0])
{
st = -trie[nod][0] + 1;
dr = i;
}
else if (st == -trie[nod][0] + 1)
if (dr > i)
dr = i;
}
printf ("%d %d %d\n", Max, st, dr);
}
int
main ()
{
freopen ("xormax.in", "rt", stdin);
freopen ("xormax.out", "wt", stdout);
read ();
solve ();
return 0;
}