Pagini recente » Cod sursa (job #264592) | Cod sursa (job #2581769) | Cod sursa (job #3283875) | Cod sursa (job #1547801) | Cod sursa (job #2771008)
#include <fstream>
#include <iostream>
using namespace std;
int n;
int a[100001];
int Max;
struct trie {
int nr;
int indcuv;
trie *bin[2];
trie () {
nr = indcuv = 0;
for (int i = 0; i < 2; i++)
bin[i] = 0;
}
};
void read() {
int i;
ifstream f("xormax.in");
f >> n;
for (i = 1; i <= n; i++)
f >> a[i];
f.close();
}
int biti[21];
int indstart, st, dr;
trie* root = new trie();
void insert(trie* nod, int biti[], int ind, int i) {
if (i == -1)
nod->indcuv = ind;
else {
if (nod->bin[biti[i]] == 0) {
nod->bin[biti[i]] = new trie();
nod->nr++;
}
insert(nod->bin[biti[i]], biti, ind, i - 1);
}
}
int search(trie* nod, int biti[], int i) {
if (i == -1) {
indstart = nod->indcuv;
return 0;
}
else {
int inv = 1 - biti[i];
if (nod->bin[inv] != 0)
return (1 << i) + search(nod->bin[inv], biti, i - 1);
else return search(nod->bin[biti[i]], biti, i - 1);
}
return 0;
}
void solve() {
int i, j, sumxor = 0, x;
Max = a[1]; st = 1, dr = 1;
for (i = 1; i <= n; i++) {
sumxor^= a[i];
for (j = 0; j <= 20; j++)
if (sumxor & (1 << j))
biti[j] = 1;
else biti[j] = 0;
if (i > 1) {
x = search(root, biti, 20);
if (x > Max) {
Max = x;
st = indstart + 1;
dr = i;
}
}
insert(root, biti, i, 20);
}
}
void output() {
ofstream g("xormax.out");
g << Max << ' ' << st << ' ' << dr;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}