Cod sursa(job #1506427)

Utilizator victor1Vasilescu Victor victor1 Data 20 octombrie 2015 17:39:13
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int lmax= 2097152;

int nodes= 0;
int pos[lmax+1], nr[lmax+1], v[lmax+1][2];

void newnode( int x) {
    for ( int i= 20, node= 0; i>=0; --i ) {
        int bit= 0;
        if ( (x&(1<<i))>0 ) {
            bit= 1;
        }

        if ( v[node][bit]==0 ) {
            ++nodes;
            v[node][bit]= nodes;
            nr[nodes]= bit;
            node= nodes;
        } else {
            node= v[node][bit];
        }
    }
}

int find_best( int x ) {
    int sol= 0;
    for ( int i= 20, node= 0; i>=0; --i ) {
        int bit= 0;
        if ( (x&(1<<i))>0 ) {
            bit= 1;
        }

        if ( v[node][1-bit]>0 ) {
            node= v[node][1-bit];
            sol= sol+((1-bit)*(1<<i));
        } else {
            node= v[node][bit];
            sol= sol+(bit*(1<<i));
        }
    }

    return sol;
}

int main(  ) {
    int n, sol= 0, start= 0, stop= 0;
    fin>>n;
    for ( int i= 1, x, aux= 0; i<=n; ++i ) {
        fin>>x;
        aux^= x;

        if ( i==1 ) {
            sol= aux;
            start= stop= 1;
        } else {
            int k= find_best(aux);
            if ( (k^aux)>sol ) {
                sol= (k^aux);
                start= pos[k]+1;
                stop= i;
            }
        }
        newnode(aux);
        pos[aux]= i;
    }

    fout<<sol<<" "<<start<<" "<<stop<<"\n";

    return 0;
}