Pagini recente » Cod sursa (job #222363) | Cod sursa (job #1353438) | Cod sursa (job #2478546) | Cod sursa (job #2399114) | Cod sursa (job #2832003)
#include <bits/stdc++.h>
#define nMax 200005
#define ll long long
using namespace std;
inline void fastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int N;
int a[nMax];
struct nod {
int nr = -1; // not strictly necessary
int endIndex = -1;
nod *st = nullptr, *dr = nullptr;
};
void addNode(nod *node, int x, int bit, int index) {
if (bit == -1) {
node->endIndex = index;
node->nr = x;
return;
}
if (x & (1 << bit)) {
if (node->dr == nullptr)
node->dr = new nod;
addNode(node->dr, x, bit - 1, index);
} else {
if (node->st == nullptr)
node->st = new nod;
addNode(node->st, x, bit - 1, index);
}
}
void findBestXor(nod *node, int crtXor, int bit, int &result, int &index) {
if (bit == -1) {
if(node->endIndex != -1)
index = node->endIndex;
return;
}
if ((crtXor & (1 << bit)) && node->st != nullptr) {
result |= (1 << bit);
if (node->endIndex != -1)
index = node->endIndex;
findBestXor(node->st, crtXor, bit - 1, result, index);
} else if (!(crtXor & (1 << bit)) && node->dr != nullptr) {
if (node->endIndex != -1)
index = node->endIndex;
result |= (1 << bit);
findBestXor(node->dr, crtXor, bit - 1, result, index);
} else if (node->st != nullptr)
findBestXor(node->st, crtXor, bit - 1, result, index);
else if (node->dr != nullptr)
findBestXor(node->dr, crtXor, bit - 1, result, index);
}
nod *r;
int main() {
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
r = new nod;
fin >> N;
for (int i = 1; i <= N; i++) {
fin >> a[i];
a[i] ^= a[i - 1];
}
int mx = 0, start = -1, end = -1;
for (int i = 1; i <= N; i++) {
if (a[i] > mx) {
mx = a[i];
end = i, start = 0;
}
int result = 0, index = -1;
findBestXor(r, a[i], 31, result, index);
if (result > mx) {
mx = result;
end = i, start = index;
}
addNode(r, a[i], 31, i);
}
fout << mx << ' ' << start + 1 << ' ' << end << '\n';
}