Pagini recente » Cod sursa (job #2240342) | Cod sursa (job #393284) | Cod sursa (job #1341609) | Cod sursa (job #2584868) | Cod sursa (job #2457465)
#include <bits/stdc++.h>
#define maxi 100009
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
struct trie
{
trie *next[2];
int last;
int val;
trie()
{
this -> val = 0;
this -> last = 0;
this -> next[0] = NULL;
this -> next[1] = NULL;
}
};
trie *root = new trie();
namespace task
{
void add(trie *nod, const int val, const int id, int bit)
{
if (bit == -1) // asta e "frunza"
{
nod -> last = id;
nod -> val = val;
return;
}
int x = (val & (1 << bit));
if (x > 0)
x = 1;
if (nod -> next[x] == nullptr)
nod -> next[x] = new trie();
add (nod -> next[x], val, id, bit - 1);
}
trie *query(trie *nod, const int val, int bit)
{
if (bit == -1)
return nod;
int x = (val & (1 << bit));
if (x > 0)
x = 1;
assert(nod -> next[0] != nullptr || nod -> next[1] != nullptr);
assert ((!x) == 0 || (!x) == 1);
if (nod -> next[!x] != nullptr)
return query(nod -> next[!x], val, bit - 1);
else
{
assert(nod -> next[x] != nullptr);
return query(nod -> next[x], val, bit - 1);
}
}
}
int main()
{
int n;
f >> n;
task::add(root, 0, 0, 25);
int Xor = 0;
int max = 0, start = 1, stop = 1;
for (int i = 1; i <= n; ++ i)
{
int a;
f >> a;
Xor = Xor ^ a;
auto Q = task::query(root, Xor, 25);
assert(Q != nullptr);
if ((Q -> val ^ Xor) > max)
{
max = Q -> val ^ Xor;
start = Q -> last + 1;
stop = i;
}
task::add(root, Xor, i, 25);
}
g << max << " " << start << " " << stop;;
}