Pagini recente » Cod sursa (job #983152) | Cod sursa (job #2531181)
#include <fstream>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
struct trie
{
trie *kid[2];
trie()
{
kid[0] = kid[1] = 0;
}
};
trie *root = new trie;
void ins(int x)
{
trie *cur = root;
for (int bit = 20; bit >= 0; bit--)
{
int cb;
if (x & (1 << bit))
{
cb = 1;
}
else
{
cb = 0;
}
if (!(cur->kid[cb]))
{
cur->kid[cb] = new trie;
}
cur = cur->kid[cb];
}
}
int fmax(int x)
{
trie *cur = root;
int sol = 0;
for (int bit = 20; bit >= 0; bit--)
{
if (!(cur->kid[0]) && !(cur->kid[0]))
{
break;
}
int cb;
if (x & (1 << bit))
{
cb = 0;
}
else
{
cb = 1;
}
if (cur->kid[cb])
{
sol += (1 << bit);
cur = cur->kid[cb];
}
else
{
cur = cur->kid[1 ^ cb];
}
}
return sol;
}
const int N = 100000 + 7;
int main()
{
int n, sol = 0, x[N], one = 1, two;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i];
x[i] ^= x[i - 1];
int now = fmax(x[i]);
if (now > sol)
{
sol = now;
two = i;
}
ins(x[i]);
}
one = two;
while (x[one - 1] != (x[two] ^ sol))
{
one--;
}
cout << sol << " " << one << " " << two << "\n";
}