Pagini recente » Cod sursa (job #2314527) | Cod sursa (job #1634266) | Cod sursa (job #2473023) | Cod sursa (job #1423292) | Cod sursa (job #282739)
Cod sursa(job #282739)
#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;
int lnod, rnod;
Trie *ins(Trie *p, int nr, int mask, int poz)
{
if (mask >= 0) {
Trie * &Dest = p->fiu[(nr >> mask) & 1];
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;
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->care, rnod = n->care, 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 = mbits-1;
for (i = 1; i <= N; ++i) {
ins(Root, A[i], mask, i);
}
guess(Root->fiu[1], 1, 1);
fo << xormax << " " << min(lnod,rnod)+1 << " " << max(lnod,rnod) << "\n";
fo.close();
return 0;
}