Pagini recente » Cod sursa (job #1496349) | Cod sursa (job #3125279) | Cod sursa (job #622230) | Cod sursa (job #2832882) | Cod sursa (job #2909593)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int SIGMA = 2;
const int DEPTH = 20;
const int INF = 1e9;
const int VMAX = (1 << 21) - 1;
int N;
int xuma, xuma0;
int maxi, start, stop;
struct Node {
int pos;
Node* children[SIGMA];
Node () {
pos = 0;
for(int i = 0; i < SIGMA; i++) {
children[i] = nullptr;
}
}
};
Node root;
void Insert(Node *root, int value, int pos, int index) {
if(index >= 0) {
bool x = (value & (1 << index)) != 0;
if(root->children[x] == nullptr) {
root->children[x] = new Node ();
}
Insert(root->children[x], value, pos, index - 1);
} else {
root->pos = max(root->pos, pos);
}
}
void Insert(int value, int pos) {
Insert(&root, value, pos, DEPTH);
}
pair<int, int> Prefix(Node *root, int value, int index, int answer = 0) {
if(index >= 0) {
bool x = (value & (1 << index)) != 0;
if(root->children[x] == nullptr) {
x ^= 1;
}
return Prefix(root->children[x], value, index - 1, answer + x * (1 << index));
} else {
return {answer, root->pos};
}
}
pair<int, int> Prefix(int value) {
return Prefix(&root, value, DEPTH, 0);
}
int main () {
fin >> N;
maxi = -INF;
Insert(0, 0);
for(int i = 1; i <= N; i++) {
int x;
fin >> x;
xuma ^= x; // hahaha ce amuzat, te-ai prins?
pair<int, int> p = Prefix(xuma ^ VMAX);
xuma0 = p.first;
if((xuma ^ xuma0) > maxi) {
maxi = (xuma ^ xuma0);
stop = i;
start = p.second + 1;
}
Insert(xuma, i);
}
fout << maxi << " " << start << " " << stop << '\n';
return 0;
}