Cod sursa(job #2015978)

Utilizator robx12lnLinca Robert robx12ln Data 28 august 2017 12:52:48
Problema Xor Max Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<fstream>
#include<cmath>
#define DIM 100000
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int s[DIM], n, P, S, sol, st, dr, E;
struct trie{
    int poz;
    trie *next[2];
    trie(){
        this->poz = 0;
        this->next[0] = this->next[1] = NULL;
    }
};
trie *rad;
void Insert( trie *nod, int x, int p, int i ){
    if( p == -1 ){
        nod->poz = max( nod->poz, i );
    }else{
        int bit = ( (x>>p) & 1 );
        if( nod->next[bit] == NULL ){
            nod->next[bit] = new trie();
        }
        Insert( nod->next[bit], x, p - 1, i );
    }
    return;
}
void query( trie *nod, int x, int p ){
    if( p == -1 ){
        P = nod->poz;
    }else{
        int bit = ( (x>>p) & 1 );
        if( nod->next[!bit] == NULL ){
            S += (1<<p) * (bit);
            query( nod->next[bit], x, p - 1 );
        }else{
            S += (1<<p) * (!bit);
            query( nod->next[!bit], x, p - 1 );
        }
    }
    return;
}
int main(){
    fin >> n;
    rad = new trie();
    for( int i = 1; i <= n; i++ ){
        fin >> s[i];
        s[i] = s[i] ^ s[i - 1];
        if( sol < s[i] ){
            sol = s[i];
            st = 1;
            dr = i;
        }
        E = max( E, ilogb( s[i] ) );
    }
    E++;
    Insert( rad, 0, E, 0 );
    for( int i = 1; i <= n; i++ ){
        P = S = 0;
        query( rad, s[i], E );
        if( sol < (S ^ s[i]) ){
            sol = (S ^ s[i]);
            st = P + 1;
            dr = i;
        }
        Insert( rad, s[i], E, i );
    }
    fout << sol << " " << st << " " << dr;
    return 0;
}