Pagini recente » Cod sursa (job #1997927) | Cod sursa (job #2551745) | Cod sursa (job #713093) | Cod sursa (job #2569659) | Cod sursa (job #601833)
Cod sursa(job #601833)
#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 = 0;
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;
}