Pagini recente » Cod sursa (job #1091448) | Cod sursa (job #2529475) | Cod sursa (job #620917) | Cod sursa (job #1356176) | Cod sursa (job #2730344)
#include <iostream>
#include <cstdio>
using namespace std;
const int LOGX = 20;
const int NMAX = 100000;
class nod {
public:
int dr;
nod *fii[2];
nod() {
dr = 0;
fii[0] = fii[1] = nullptr;
}
};
class trie {
private:
nod *root;
void add_nr(nod *crt_root, int nr, int p2, int dr) {
if(p2 == 0)
return;
if(p2 == 1)
crt_root->dr = dr;
int bit = (nr & p2) == 0 ? 0 : 1;
if(!crt_root->fii[bit])
crt_root->fii[bit] = new nod;
add_nr(crt_root->fii[bit], nr, p2 >> 1, dr);
}
int get_xor_max(nod *crt_root, int nr, int p2, int &dr) {
if(p2 == 0)
return 0;
if(p2 == 1)
dr = crt_root->dr;
int best = ((nr & p2) ^ p2) == 0 ? 0 : 1;
if(!crt_root->fii[best])
best = 1 - best;
return (p2 * best) | get_xor_max(crt_root->fii[best], nr, p2 >> 1, dr);
}
public:
trie() {
root = new nod;
}
void add_nr(int nr, int dr) {
add_nr(root, nr, 1 << LOGX, dr);
}
int get_xor_max(int nr, int &dr) {
return get_xor_max(root, nr, 1 << LOGX, dr);
}
};
int xor_prefix[NMAX + 5];
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int n, xor_all = 0;
trie tr;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &xor_prefix[i]);
xor_prefix[i] ^= xor_prefix[i - 1];
}
xor_all = xor_prefix[n + 1] = xor_prefix[n];
int xor_sufix = 0, xor_max = -1, max_st = 0, max_dr = 0;
for(int l = n - 1; l >= 0; l--) {
xor_sufix ^= (xor_prefix[l + 2] ^ xor_prefix[l + 1]); /// adaug la sufix nr din sirul initial de pe pozitia l + 2
tr.add_nr(xor_sufix, l + 2);
int crt_dr;
int xor_right = xor_all ^ xor_prefix[l]; /// xor_right = suma ^ pt nr din sirul initial de pe poz l+1 ... n
int xor_crt = xor_right ^ tr.get_xor_max(xor_right, crt_dr); /// caut sufixul pt care xor_right ^ sufix este maxim
if(xor_crt > xor_max || (xor_crt == xor_max && crt_dr - 1 < max_dr) )
xor_max = xor_crt, max_st = l + 1, max_dr = crt_dr - 1;
}
printf("%d %d %d", xor_max, max_st, max_dr);
return 0;
}