Pagini recente » Cod sursa (job #2255578) | Cod sursa (job #3166036)
#include <bits/stdc++.h>
using namespace std;
int sp[100001], cur_left;
struct node {
node *f[2];
int in_nr, cuv;
node() {
f[1] = f[0] = NULL;
in_nr = 0, cuv = 0;
}
};
void update(node *root, int x, int ind) {
node *curr = root;
for(int i = 21; i > -1; i --) {
bool ok = (((1 << i) & x) > 0);
if(curr->f[ok] == NULL) {
curr->f[ok] = new node;
}
curr = curr->f[ok];
curr->in_nr ++;
}
curr->cuv = ind;
}
int max_xor(node *root, int x) {
cout << "PENTRU " << x << endl << endl;
int xor_max = 0;
node *curr = root;
for(int i = 21; i > -1; i --) {
bool ok = (((1 << i) & x) > 0);
cout << "inv bit " << (1 << i) << " ese ";
if(ok == 1) {
ok = 0;
} else {
ok = 1;
}
cout << ok << endl;
if(curr->f[ok] != NULL) {
cout << "il putem lua\n";
xor_max += (1 << i);
curr = curr->f[ok];
} else if(curr->f[(ok == 1 ? ok = 0 : ok = 1)] != NULL) {
cout << "nu il putem lua\n";
curr = curr->f[ok];
}
}
cout << endl;
cur_left = curr->cuv;
return xor_max;
}
int main() {
ifstream cin("xormax.in");
ofstream cout("xormax.out");
node *root = new node;
int n;
cin >> n;
for(int i = 1; i <= n; i ++) {
int a;
cin >> a;
sp[i] = (sp[i - 1] ^ a);
update(root, sp[i], i);
}
int ans = 0, l, r;
for(int i = 1; i <= n; i ++) {
int maxx = max_xor(root, sp[i]);
maxx = max(maxx, sp[i] ^ sp[i - 1]);
if(maxx > ans) {
ans = maxx;
if(i >= cur_left) {
l = cur_left + 1;
r = i;
} else {
r = cur_left;
l = i + 1;
}
} else if(ans == maxx) {
int st = min(i, cur_left) + 1;
int dr = max(i, cur_left);
if(dr >= r) {
dr = r;
l = st;
}
}
}
cout << ans << " " << l << " " << r;
node *curr = root;
return 0;
}