Pagini recente » Cod sursa (job #514763) | Cod sursa (job #818199) | Cod sursa (job #1416584) | Cod sursa (job #1604277) | Cod sursa (job #1110308)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int MAXBIT = 5;//22;
struct Trie {
Trie *son[2];
int start;
Trie() {
memset(son, 0, sizeof son);
start = -1;
}
};
Trie *trie = new Trie;
int n, curXOR = 0;
void init (int poz, Trie *cur) {
if (poz == -1) {
cur->start = 1;
return;
}
cur->son[0] = new Trie;
init(poz - 1, cur->son[0]);
}
int test (int poz, int &best, int a, Trie *cur) {
if (poz == -1) {
return cur->start;
}
int bit = ((1 << poz) & a) != 0;
bit = bit ^ ((curXOR & (1 << poz)) != 0);
if (cur->son[1] == 0) {
best += (1 << poz) * bit;
return test (poz - 1, best, a, cur->son[0]);
}
else if (cur->son[0] == 0) {
best += (1 << poz) * !bit;
return test (poz - 1, best, a, cur->son[1]);
}
else {
best += (1 << poz);
return test (poz - 1, best, a, cur->son[!bit]);
}
return -1;
}
void adauga (int poz, int &st, int a, Trie *cur) {
if (poz == -1) {
cur->start = st;
return;
}
int bit = ((1 << poz) & a) != 0;
int type = (curXOR & (1 << poz)) != 0;
if (cur->son[type] == 0)
cur->son[type] = new Trie;
adauga (poz - 1, st, a, cur->son[type]);
if (bit) curXOR ^= (1 << poz);
}
int main() {
fin >> n;
init(MAXBIT, trie);
int bestst, bestfn, best = -1;
for (int i = 1; i <= n; ++i) {
int a; fin >> a;
int curBest = 0, newstart;
newstart = test(MAXBIT, curBest, a, trie);
if (curBest > best) {
best = curBest;
bestst = newstart;
bestfn = i;
}
adauga(MAXBIT, i, a, trie);
}
fout << best << " " << bestst << " " << bestfn << "\n";
return 0;
}