Pagini recente » Cod sursa (job #690438) | Cod sursa (job #1514829) | Cod sursa (job #1987624) | Cod sursa (job #1647964) | Cod sursa (job #2101259)
#include<fstream>
using namespace std;
ifstream in ("xormax.in");
ofstream out ("xormax.out");
int y,alfa,beta,num;
struct trie {
trie *bit[2];
int numar;
trie() {
bit[0] = NULL;
bit[1] = NULL;
numar = 0;
}
};
int p[23],n,v[100001],maxim;
bool s[23];
trie *radacina = new trie;
void change (int x) {
int k = -1;
for (int i = 0; i <= 21; i ++) {
s[i] = 0;
}
while (x > 0) {
s[++k] = x % 2;
x /= 2;
}
for (int i = 0; i <= 11; i ++) {
swap (s[i],s[21-i]);
}
return;
}
void adauga (trie *&nod, int i, int dr) {
if (i == 22) {
nod -> numar = dr;
return;
}
if (nod -> bit[s[i]] == NULL) {
nod -> bit[s[i]] = new trie;
}
adauga(nod -> bit[s[i]], i + 1,dr);
return;
}
int cauta (trie *&nod, int i) {
if (i == 22) {
y = nod -> numar;
return 0;
}
if (nod -> bit[1-s[i]] != NULL) {
return p[(21-i)] + cauta(nod -> bit[1-s[i]],i+1);
}
else {
return cauta(nod -> bit[s[i]],i+1);
}
}
int main (void) {
in >> n;
for (int i = 1; i <= n; i ++) {
in >> v[i];
}
for (int i = 1; i <= n; i ++) {
v[i] = v[i] xor v[i-1];
}
p[0] = 1;
for (int i = 1; i <= 22; i ++) {
p[i] = p[i-1] * 2;
}
maxim = -1;
change(0);
adauga (radacina,0,0);
for (int i = 1; i <= n; i ++) {
change(v[i]);
num = cauta(radacina,0);
if (num > maxim) {
maxim = num;
alfa = i;
beta = y;
}
adauga (radacina,0,i);
}
out << maxim << " " << beta + 1 <<" "<< alfa <<" ";
return 0;
}