Pagini recente » Cod sursa (job #2458628) | Cod sursa (job #1971453) | Cod sursa (job #3194047) | Cod sursa (job #202517) | Cod sursa (job #2885995)
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
// #define f cin
// #define g cout
struct trie
{
int lastpoz;
trie *next[2];
trie()
{
lastpoz = -1;
next[0] = next[1] = nullptr;
}
} *root = new trie;
int n, prexor, mxm, le, ri;
void add(int, int);
pair<int, int> getbest(int);
int32_t main()
{
f >> n;
add(0, 0);
for (int i = 1, ax, x; i <= n; i++)
{
static pair<int, int> r;
f >> x;
prexor ^= x;
r = getbest(prexor);
ax = prexor ^ r.first;
if (ax > mxm)
mxm = ax, le = r.second, ri = i;
add(prexor, i);
}
g << mxm << " " << le + 1 << " " << ri;
return 0;
}
void add(int x, int poz)
{
trie *ax = root;
for (int i = 20, r; i >= 0; i--)
{
r = !!(x & (1 << i));
if (ax->next[r] == nullptr)
ax->next[r] = new trie;
ax = ax->next[r];
}
ax->lastpoz = poz;
}
pair<int, int> getbest(int x)
{
int nr = 0;
trie *ax = root;
pair<int, int> rez;
for (int i = 20, r; i >= 0; i--)
{
r = !(!!(x & (1 << i)));
if (ax->next[r] != nullptr)
ax = ax->next[r], nr |= r * (1 << i);
else
ax = ax->next[!r], nr |= (!r) * (1 << i);
}
return make_pair(nr, ax->lastpoz);
}