Pagini recente » Cod sursa (job #2057466) | Cod sursa (job #2337232) | Cod sursa (job #259009) | Cod sursa (job #1516829) | Cod sursa (job #285875)
Cod sursa(job #285875)
#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 = 1, rnod = 1;
void 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 = 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 >> shift) & 1)
void guess(int which) {
int tmp, config = A[which];
int shift = mbits;
Trie *n = Root;
while (shift--) {
n = n->fiu[!lbit] ? n->fiu[!lbit] :
n->fiu[lbit];
}
// check it !
if ((tmp = config ^ A[n->care]) > xormax) { // sau egal !
lnod = n->care+1, rnod = which, xormax = tmp;
}
}
int main()
{
int i, x, mask;
fi >> N;
Trie *a = new Trie;
for (i = 1; i <= N; ++i) {
fi >> x;
A[i] = A[i-1] ^ x;
mbits = max(bits(A[i]), mbits);
}
mask = mbits-1;
for (i = 1; i <= N; ++i) {
if (i > 1) guess(i);
ins(Root, A[i], mask, i);
}
// guess i, mbits
fo << xormax << " " << lnod << " " << rnod << "\n";
fo.close();
return 0;
}