Pagini recente » Cod sursa (job #2943931) | Cod sursa (job #2893872) | Cod sursa (job #1623332) | Borderou de evaluare (job #1036217) | Cod sursa (job #3239019)
#include <iostream>
#include <fstream>
#define NMAX 1000005
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, s[NMAX];
struct Node {
int ind;
Node* sons[2];
Node() : ind(-1), sons{nullptr, nullptr} {}
};
Node* root = new Node;
void add(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;
}
add(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 element, maxim = 0, start = 0, finish = 0;
fin >> n;
if (n > 0) {
fin >> s[0];
add(root, 0, 20);
for (int i = 1; i < n; ++i) {
fin >> element;
s[i] = s[i - 1] ^ element;
int pozBest = getBest(root, i, 20);
int xorVal = s[i] ^ s[pozBest];
if (xorVal > maxim) {
start = pozBest + 1;
finish = i;
maxim = xorVal;
}
add(root, i, 20);
}
}
fout << maxim << ' ' << start + 1 << ' ' << finish + 1;
return 0;
}