Pagini recente » Borderou de evaluare (job #1801933) | Borderou de evaluare (job #1280961) | Borderou de evaluare (job #1936944) | Borderou de evaluare (job #1400518) | Cod sursa (job #3274393)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int BMax = 29;
struct Nod {
Nod* fii[2];
int poz;
Nod(int _poz = 0) {
poz = _poz;
fii[0] = fii[1] = nullptr;
}
~Nod() {
delete fii[0];
delete fii[1];
}
} *radTrie;
int n, i, sumX[100002], rasp, st, dr;
static inline void Add(int val, int poz, int bit = BMax, Nod* nodCur = radTrie) {
if(bit == -1) return;
bool bitCur = (val >> bit & 1);
if(nodCur->fii[bitCur] == nullptr) {
nodCur->fii[bitCur] = new Nod(poz);
}
Add(val, poz, bit - 1, nodCur->fii[bitCur]);
}
static inline int Search(const int val, int bit = BMax, Nod* nodCur = radTrie) {
if(bit == -1) return nodCur->poz;
bool bitCur = (val >> bit & 1);
if(nodCur->fii[!bitCur] != nullptr) return Search(val, bit - 1, nodCur->fii[!bitCur]);
if(nodCur->fii[ bitCur] != nullptr) return Search(val, bit - 1, nodCur->fii[ bitCur]);
return nodCur->poz;
}
int main() {
//ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
radTrie = new Nod(0);
fin >> n;
Add(0, 0);
for(i = 1; i <= n; i++) {
fin >> sumX[i];
sumX[i] ^= sumX[i - 1];
int caut = Search(sumX[i]);
if(rasp < (sumX[i] ^ sumX[caut])) {
rasp = sumX[i] ^ sumX[caut];
st = caut + 1;
dr = i;
}
else if(rasp == (sumX[i] ^ sumX[caut])) {
if(st > caut + 1) st = caut + 1, dr = i;
}
Add(sumX[i], i);
}
fout << rasp << " " << st << " " << dr;
delete radTrie;
return 0;
}