Pagini recente » Cod sursa (job #1501561) | Cod sursa (job #936119) | Cod sursa (job #1973651) | Cod sursa (job #1417946) | Cod sursa (job #1814168)
#include <fstream>
#include <cstring>
using namespace std;
const int NMaX = 100005, StartBitPow = 20, INF = 0x3f3f3f3f;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int v[NMaX];
int n, st, ed, max_xor = -INF;
struct Trie{
int pos;
Trie *children[2];
Trie() {
memset( children, 0, sizeof( children ) );
}
};
Trie *T = new Trie;
int Query(Trie *node, int val, int pow){
if(pow < 0){
return node->pos;
}
int best_dir = (val & (1 << pow)) == 0;
if(node->children[best_dir] == nullptr){
//node->children[!best_dir] = new Trie;
return Query(node->children[!best_dir], val, pow - 1);
}
return Query(node->children[best_dir], val, pow - 1);
}
void Add(Trie *node, int val, int ind, int pow){
if(pow < 0){
node->pos = ind;
return;
}
int dir = (val & (1 << pow)) == 0;
if(node->children[!dir] == nullptr){
node->children[!dir] = new Trie;
}
Add(node->children[!dir], val, ind, pow - 1);
}
int main() {
int i, best_pos, best_val;
fin>>n;
Add(T, 0, 0, StartBitPow);
for(i = 1; i <= n; ++i){
fin>>v[i];
v[i] ^= v[i - 1];
best_pos = Query(T, v[i], StartBitPow);
best_val = v[best_pos];
if((best_val ^ v[i]) > max_xor){
max_xor = best_val ^ v[i];
st = best_pos + 1;
ed = i;
}
Add(T, v[i], i, StartBitPow);
}
fout<< max_xor << " " << st << " " << ed;
return 0;
}