Pagini recente » Cod sursa (job #1579711) | Cod sursa (job #2142494) | Cod sursa (job #2121693) | Cod sursa (job #1111908) | Cod sursa (job #1739707)
// consideram sumele xor partiale si scrierile lor pe acelasi numar de biti
// (numarul maxim de biti necesari pentru scrierea vreuneia).
// inseram intr-un trie scrierile in baza 2 ale acestor sume (incepand cu BITUL CEL MAI
// SEMNIFICATIV) dar, inainte sa inseram suma curenta interogam trie-ul (care contine sumele
// de pe pozitiile anterioare!) si cautam pe una care sa difere, in primul rand printr-un bit
// cat mai de sus si tot asa pentru urmatorii biti ...
#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;
}