Pagini recente » Cod sursa (job #2273559) | Cod sursa (job #1655735) | Cod sursa (job #2666588) | Cod sursa (job #2449153) | Cod sursa (job #601837)
Cod sursa(job #601837)
#include <iostream>
using namespace std;
#define maxTrie (1 << 22)
#define maxN 100005
int Trie[maxTrie], A[maxN];
int Pos[maxTrie], poz1, poz2;
inline int brother (int X)
{
if (X % 2) return X - 1;
return X + 1;
}
void build_trie (int X, int poz)
{
int start;
int bit = 20;
if (X & (1 << bit)) start = 3;
else start = 2;
Trie[start] = true;
-- bit;
for ( ; bit >= 0; -- bit)
if ( X & (1 << bit) )
{
start *= 2;
++ start;
Trie[start] = true;
}
else
{
start *= 2;
Trie[start] = true;
}
Pos[X] = poz;
}
int search (int X)
{
int start, nr = 0;
int bit = 20;
if (X & (1 << bit)) start = 2;
else start = 3;
if (Trie[start]) nr += (start % 2) * (1 << bit);
else
{
start = brother (start);
nr += (start % 2) * (1 << bit);
}
-- bit;
for ( ; bit >= 0; -- bit)
if ( X & (1 << bit) )
{
start *= 2;
if (Trie[start]) nr += (start % 2) * (1 << bit);
else
{
start = brother (start);
nr += (start % 2) * (1 << bit);
}
}
else
{
start *= 2;
++ start;
if (Trie[start]) nr += (start % 2) * (1 << bit);
else
{
start = brother (start);
nr += (start % 2) * (1 << bit);
}
}
return nr;
}
int main()
{
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
int N, sum = 0, max = - 1;
scanf ("%d", &N);
build_trie (sum, 0);
for (int i = 1; i <= N; ++ i)
{
scanf ("%d", &A[i]);
sum ^= A[i];
int found = search (sum);
if ((sum ^ found) > max)
{
max = (sum ^ found);
poz1 = Pos[found] + 1;
poz2 = i;
}
build_trie (sum, i);
}
printf ("%d %d %d", max, poz1, poz2);
return 0;
}