Pagini recente » Cod sursa (job #2978226) | Cod sursa (job #2801587) | Cod sursa (job #342995) | Cod sursa (job #650877) | Cod sursa (job #2530590)
#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, 21);
for (int i = 1; i < N; ++i) {
fin >> aux;
s[i] = s[i - 1] ^ aux;
int pozBest = getBest(root, i, 21);
int xorValue = s[i] ^ s[pozBest];
if (xorValue > maxi) {
st = pozBest + 1;
fn = i;
maxi = xorValue;
}
addNumber(root, i, 21);
}
fout << maxi << " " << st + 1 << " " << fn + 1 << "\n";
return 0;
}