Pagini recente » simulareoji_2007_11-12 | Cod sursa (job #1166440) | Cod sursa (job #69052) | Cod sursa (job #1333533) | Cod sursa (job #1739706)
#include <fstream>
#define DIM 100010
using namespace std;
int maxim, stmaxim, drmaxim, n, maxx, nr, pozsol, x;
int s[DIM];
struct trie {
trie *f[2];
int poz;
trie () {
f[0] = f[1] = 0;
poz = 0;
}
};
trie *r;
void inserare(trie *r, int bit, int val, int poz) {
if (bit == -1) {
r->poz = poz;
return;
}
if (((val>>bit) & 1) == 0) {
if (r->f[0] == NULL)
r->f[0] = new trie();
inserare(r->f[0], bit-1, val, poz);
} else {
if (r->f[1] == NULL)
r->f[1] = new trie();
inserare(r->f[1], bit-1, val, poz);
}
}
void cauta(trie *r, int bit, int val) {
if (bit == -1) {
pozsol = r->poz;
return;
}
int bitval = ((val >> bit) & 1);
if (r->f[1-bitval] != 0) {
cauta(r->f[1-bitval], bit-1, val);
} else {
cauta(r->f[bitval], bit-1, val);
}
}
int main () {
ifstream fin ("xormax.in");
ofstream fout("xormax.out");
fin>>n>>s[1];
maxim = -1;
for (int i=2;i<=n;i++) {
fin>>x;
if (x > maxx)
maxx = x;
s[i] = (x ^ s[i-1]);
}
while (maxx) {
nr++;
maxx/=2;
}
r = new trie();
inserare(r, nr, 0, 0);
for (int i=1;i<=n;i++) {
cauta(r, nr, s[i]);
if ((s[i] ^ s[pozsol]) > maxim) {
maxim = (s[i] ^ s[pozsol]);
stmaxim = pozsol+1;
drmaxim = i;
}
inserare(r, nr, s[i], i);
}
fout<<maxim<<" "<<stmaxim<<" "<<drmaxim;
return 0;
}