Cod sursa(job #2293334)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 30 noiembrie 2018 21:27:16
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#define DIM 100010
using namespace std;

ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
int v[DIM];
int n,i,maxim,sol,ap,st,dr;
struct trie{
    int poz;
    trie *f[2];
    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){
        sol = r->poz;
        return;
    }

    int nr = ((val>>bit)&1);
    if (r->f[1-nr] != 0)
        cauta (r->f[1-nr],bit-1,val);
    else
        cauta (r->f[nr],bit-1,val);

}

int main (){

    fin>>n;
    fin>>v[1];
    maxim = -2000000000;
    for (i=2;i<=n;i++){
        fin>>v[i];
        maxim = max (maxim,v[i]);
        v[i] = v[i]^v[i-1];
    }
    ap = 0;
    while (maxim){
        ap++;
        maxim /= 2;
    }

    r = new trie();
    inserare (r,ap,0,0);
    maxim = -2000000000;
    for (i=1;i<=n;i++){
        cauta (r,ap,v[i]);
        if ( (v[i]^v[sol]) > maxim){
            maxim = (v[i]^v[sol]);
            st = sol+1;
            dr = i;
        }
        inserare (r,ap,v[i],i);
    }

    fout<<maxim<<" "<<st<<" "<<dr;

    return 0;
}