Pagini recente » Profil Irispetre | Rating popescu gabriela (ella) | Cod sursa (job #2099163) | Cod sursa (job #355995) | Cod sursa (job #2018067)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int NMAX = 100000;
const int DIM = 1000000;
struct Trie {
int pos;
Trie *fii[2];
Trie() {
pos = 0;
fii[0] = fii[1] = NULL;
}
};
int n, sol = -1;
int poz;
int le, ri, index;
int xs[1 + NMAX];
char buff[DIM];
Trie *root = new Trie;
void read(int &no){
no = 0;
while(!isdigit(buff[poz])){
if(++poz == DIM){
in.read(buff, DIM);
poz = 0;
}
}
while(isdigit(buff[poz])){
no = (no * 10) + (buff[poz] - '0');
if(++poz == DIM){
in.read(buff, DIM);
poz = 0;
}
}
}
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;
read(n);
add(root, 0, 0, 21);
for(int i = 1; i <= n; i++) {
//in >> xs[i];
read(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;
}