Pagini recente » Cod sursa (job #83073) | Cod sursa (job #633510) | Cod sursa (job #1338952) | Cod sursa (job #1638303) | Cod sursa (job #2530593)
#include <fstream>
#include <iostream>
#define MAXN 1000005
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int N, s[MAXN];
struct Node {
int ind;
Node* sons[2];
};
Node* root = new Node;
void addNumber(Node* node, int poz, int bitNumber) {
if (bitNumber == 0) {
node -> ind = poz;
return;
}
int bit = (s[poz] >> bitNumber) & 1;
if (node -> sons[bit] == nullptr) {
node -> sons[bit] = new Node;
}
addNumber(node -> sons[bit], poz, bitNumber - 1);
}
int getBest(Node* node, int poz, int bitNumber) {
if (bitNumber == 0) {
return node -> ind;
}
int bit = ((s[poz] >> bitNumber) & 1) ^ 1;
if (node -> sons[bit] != nullptr) {
return getBest(node -> sons[bit], poz, bitNumber - 1);
}
return getBest(node -> sons[bit ^ 1], poz, bitNumber - 1);
}
int main()
{
int aux, maxi = -1, st = 0, fn = 0;
fin >> N;
fin >> s[0];
addNumber(root, 0, 22);
for (int i = 1; i < N; ++i) {
fin >> aux;
s[i] = s[i - 1] ^ aux;
int pozBest = getBest(root, i, 22);
int xorValue = s[i] ^ s[pozBest];
if (xorValue > maxi) {
st = pozBest + 1;
fn = i;
maxi = xorValue;
}
addNumber(root, i, 22);
}
fout << maxi << " " << st + 1 << " " << fn + 1 << "\n";
return 0;
}