Pagini recente » Cod sursa (job #855012) | Cod sursa (job #1326917) | Cod sursa (job #2965595) | Cod sursa (job #1420722) | Cod sursa (job #282729)
Cod sursa(job #282729)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
#define MN 100001
struct Trie {
int care;
Trie* fiu[2];
} *Root = new Trie;
int N, A[MN], mbits;
int xormax = 0;
Trie *lnod, *rnod;
Trie *ins(Trie *p, int nr, int mask, int poz)
{
if (mask) {
Trie * &Dest = p->fiu[nr & mask];
if (Dest == 0)
Dest = new Trie;
ins(Dest, nr, mask>>1, poz);
} else
//p->care.push_back(poz);
p->care = poz;
}
int bits(int nr) {
// max 21
int step = 16, i;
for (i = 0; step; step >>= 1)
if (i+step <= 21 && (nr >> i+step))
i += step;
return i+1;
}
#define lbit (config & 1)
void guess(Trie *p, int config, int shift) {
int last = 1, tmp;
for (int i = 0; i < 2; ++i)
if (p->fiu[i]) {
guess(p->fiu[i], config + (i<<shift), shift+1);
last = 0;
}
if (last) {
Trie *n = Root->fiu[0];
for (; shift--; config >>= 1) {
n = n->fiu[!lbit] ? n->fiu[!lbit] :
n->fiu[lbit];
}
// check it !
if ((tmp = A[p->care] ^ A[n->care]) > xormax) // sau egal !
lnod = p, rnod = n, xormax = tmp;
}
}
int main()
{
int i, x, mask;
fi >> N;
Trie *a = new Trie;
for (i = 1; i <= N; ++i) {
fi >> x;
A[i] = i ? A[i-1] ^ x : x;
mbits = max(bits(A[i]), mbits);
}
mask = 1 << mbits-1;
for (i = 1; i <= N; ++i) {
ins(Root, A[i], mask, i);
}
guess(Root->fiu[1], 1, 1);
fo << xormax << " " << lnod->care << " " << rnod->care << "\n";
fo.close();
return 0;
}