Pagini recente » Cod sursa (job #965450) | Cod sursa (job #2448480) | Cod sursa (job #11184) | Cod sursa (job #1818700) | Cod sursa (job #3307050)
#include <algorithm>
#include <fstream>
#include <vector>
#define ll long long
using namespace std;
const string txt = "xormax";
const int nmax = 1e5 + 5;
ifstream f(txt + ".in");
ofstream g(txt + ".out");
struct trie {
trie* nxt[5];
int poz;
trie() {
nxt[0] = nxt[1] = NULL; poz = 0;
}
};
int n, v[nmax], maxi = -1, st, dr;
static void add(int x, int b, int ind, trie* nod)
{
if (b == 0) {
if (!nod -> poz)
nod -> poz = ind;
return;
}
int vec = (x & (1 << b) ? 1 : 0);
if (!nod -> nxt[vec])
nod -> nxt[vec] = new trie;
add(x, b - 1, ind, nod -> nxt[vec]);
}
static int query(int x, int b, trie* nod)
{
if (b == 0)
return nod->poz;
int vec = (x & (1 << b) ? 0 : 1);
if (!nod -> nxt[vec])
return query(x, b - 1, nod -> nxt[1 - vec]);
return query(x, b - 1, nod -> nxt[vec]);
}
int main()
{
trie* rad = new trie;
add(0, 20, 0, rad);
f >> n;
for (int i = 1; i <= n; i++)
{
int x; f >> x;
v[i] = (v[i - 1] ^ x);
int poz = query(v[i], 20, rad);
if (maxi < (v[i] ^ v[poz]))
maxi = (v[i] ^ v[poz]), st = poz + 1, dr = i;
else if (maxi == (v[i] ^ v[poz]) && st > poz + 1)
st = poz + 1, dr = i;
add(v[i], 20, i, rad);
}
g << maxi << " " << st << " " << dr;
return 0;
}