Cod sursa(job #1775048)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 9 octombrie 2016 18:51:12
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<fstream>
using namespace std;
int n, i, maxim, x, p, u, st, aux, j, sum;
int v[100005];
char s[25];
struct trie{
    int poz;
    trie *f[2];
    trie(){
        poz = 0;
        f[0] = f[1] = NULL;
    }
};
trie *r;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
void adauga(trie *r, char *s, int i){
    if(*s == -1){
        r->poz = i;
    }
    else{
        if(r->f[*s] == NULL){
            r->f[*s] = new trie;
        }
        adauga(r->f[*s], s + 1, i);
    }
}
void query(trie *r, char *s){
    if(*s == -1){
        st = r->poz;
    }
    else{
        if(*s == 0){
            if(r->f[1] == NULL){
                query(r->f[0], s + 1);
            }
            else{
                query(r->f[1], s + 1);
            }
        }
        else{
            if(r->f[0] == NULL){
                query(r->f[1], s + 1);
            }
            else{
                query(r->f[0], s + 1);
            }
        }
    }
}
int main(){
    r = new trie;
    fin>> n;
    s[20] = -1;
    maxim = -1;
    adauga(r, s, 0);
    for(i = 1; i <= n; i++){
        fin>> x;
        v[i] = (v[i - 1] ^ x);
        aux = v[i];
        for(j = 19; j >= 0; j--){
            s[j] = aux % 2;
            aux /= 2;
        }
        query(r, s);
        adauga(r, s, i);
        sum = (v[i] ^ v[st]);
        if(sum > maxim){
            maxim = sum;
            p = st + 1;
            u = i;
        }
    }
    fout<< maxim <<" "<< p <<" "<< u <<"\n";
    return 0;
}