Cod sursa(job #1274996)

Utilizator lokixdSebastian lokixd Data 24 noiembrie 2014 17:23:30
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
 
using namespace std;
 
ifstream f ("xormax.in");
ofstream g ("xormax.out");
 
struct trie {
    int pozitie;
    trie *fiu[2];
    trie() {
        pozitie = 0;
        fiu[0] = fiu[1] = NULL;
    };
};
 
const int NMAX = 100000 + 1;
 
int n;
trie *radacina;
int v[NMAX];
 
trie *adauga(trie *t, int x, int bit, int poz) {
    if (t == NULL) t = new trie;
    if (bit == -1) {
        t->pozitie = poz;
    }
    else {
        int m = x & (1 << bit);
        m = (m > 0);
        t->fiu[m] = adauga(t->fiu[m], x, bit - 1, poz);
    }
    return t;
}
 
void test(trie *t) {
    if (t == NULL) return;
    cout << t->pozitie << ' ';
    test(t->fiu[0]);
    test(t->fiu[1]);
}
 
int sol(trie *t, int x, int bit) {
    if (t == NULL) return 0;
    if (bit == -1) return t->pozitie;
    int m = x & (1 << bit);
    m = (m > 0);
    if (t->fiu[1 - m] != NULL) return sol(t->fiu[1 - m], x, bit - 1);
    return sol(t->fiu[m], x, bit - 1);
}
 
void rezolva() {
    int j;
    int bit = 20, rez = -1, a, b;
    radacina = adauga(radacina, 0, bit, 0);
    for (int i = 1; i <= n; i++) {
        f >> v[i];
        v[i] = v[i] ^ v[i - 1];
        j = sol(radacina, v[i], bit);
        if ((v[i] ^ v[j]) > rez) {
            rez = v[i] ^ v[j];
            a = j + 1;
            b = i;
        }
        radacina = adauga(radacina, v[i], bit, i);
    }
    g << rez << ' ' << a << ' ' << b << '\n';
}
 
int main() {
    f >> n;
    rezolva();
    return 0;
}