Cod sursa(job #2143430)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 25 februarie 2018 22:24:36
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>
using namespace std;
const int kMaxCells = 2100000 + 1;
int Trie[kMaxCells][2], nxt = 1;
int seqPos[kMaxCells];
inline void emplace(int x, int pos) {
int node = 0;
for (register int i = 21; i >= 0; i--) {
if (Trie[node][(x >> i) & 1] == 0) {
Trie[node][(x >> i) & 1] = nxt++;}
node = Trie[node][(x >> i) & 1];}
seqPos[node] = pos; // retine pozitia pentru nodul final}
inline pair <int, int> getMax(int x) {
int node = 0, ans = 0;
for (register int i = 21; i >= 0; i--) {
if (Trie[node][~(x >> i) & 1] != 0) {
ans |= (1 << i);
node = Trie[node][~(x >> i) & 1];
} else {
node = Trie[node][(x >> i) & 1];}}
return make_pair(ans, seqPos[node]);}
int main(void) {
ifstream in("xormax.in");
ofstream out("xormax.out");
in.tie(0);
ios_base::sync_with_stdio(0);
int n;
int xorSum, x;
int CET, posStart, posEnd;
in >> n;
CET = -1;
xorSum = 0;
emplace(0, -1); 
for (register int i = 0; i < n; i++) {
in >> x;
xorSum ^= x;
pair <int, int> q = getMax(xorSum);
if (q.first > CET) {
CET = q.first;
posStart = q.second + 1;
posEnd = i;}
emplace(xorSum, i);}
in.close();
out << CET << ' ' << posStart + 1 << ' ' << posEnd + 1 << '\n';
out.close();
return 0;}