Cod sursa(job #1498691)

Utilizator Athena99Anghel Anca Athena99 Data 8 octombrie 2015 22:35:02
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <vector>

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];
vector <int> v[lmax+1];

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

        if ( (int)v[node].size()==0 || ((int)v[node].size()==1 && nr[v[node][0]]!=bit) ) {
            ++nodes;
            v[node].push_back(nodes);
            nr[nodes]= bit;
            node= nodes;
        } else {
            if ( nr[v[node][0]]==bit ) {
                node= v[node][0];
            } else {
                node= v[node][1];
            }
        }
    }
}

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;
        }

        int ok= 0;
        for ( int j= 0; j<(int)v[node].size(); ++j ) {
            if ( nr[v[node][j]]!=bit ) {
                ok= 1;
                node= v[node][j];
                sol= sol+((1-bit)*(1<<i));
                break;
            }
        }
        if ( ok==0 ) {
            if ( i>0 ) node= v[node][0];
            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;
}