Pagini recente » Monitorul de evaluare | Statistici Ciobotaru Cosmin-Andrei (cosminnnn) | Cod sursa (job #149739) | Profil CristianMuntean | Cod sursa (job #2018066)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int NMAX = 100000;
struct Trie {
int pos;
Trie *fii[2];
Trie() {
pos = 0;
fii[0] = fii[1] = NULL;
}
};
int n, sol = -1;
int le, ri, index;
int xs[1 + NMAX];
Trie *root = new Trie;
void add(Trie *node, int s, int ind, int pos) {
if(pos < 0) {
node->pos = ind;
return;
} else {
int byte = (s >> pos) & 1;
if(node->fii[byte] == NULL)
node->fii[byte] = new Trie();
add(node->fii[byte], s, ind, pos - 1);
}
}
int query(Trie *node, int s, int pos) {
if(pos < 0) {
return node->pos;
} else {
int byte = (s >> pos) & 1;
if(node->fii[1 - byte] != NULL)
byte = 1 - byte;
return query(node->fii[byte], s, pos - 1);
}
}
void update(int from, int to) {
int pretender = xs[from] ^ xs[to];
if(sol < pretender) {
sol = pretender;
if(from < to) {
le = from + 1;
ri = to;
} else {
le = from;
ri = to;
}
}
}
int main()
{
in >> n;
add(root, 0, 0, 21);
for(int i = 1; i <= n; i++) {
in >> xs[i];
xs[i] ^= xs[i - 1];
add(root, xs[i], i, 21);
index = query(root, xs[i], 21);
update(index, i);
}
out << sol << ' ' << le << ' ' << ri << '\n';
in.close();
out.close();
return 0;
}