Pagini recente » Cod sursa (job #301470) | Cod sursa (job #235299) | Cod sursa (job #2144724) | Cod sursa (job #1667666) | Cod sursa (job #2909613)
#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, const int &value, const 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 = pos;
}
}
void Insert(const int &value, const int &pos) {
Insert(&root, value, pos, DEPTH);
}
pair<int, int> Prefix(Node *root, const int &value, const 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(const int &value) {
return Prefix(&root, value, DEPTH);
}
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;
}