Cod sursa(job #808558)

Utilizator veleanduAlex Velea veleandu Data 6 noiembrie 2012 22:02:03
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
using namespace std;

    int n,nr,i,j,rez;
    int biti[40];
    int st,dr,maxim;

    class bit {
        public:
            bit *it[2];
            int val;
        bit () {
            val=0;
        }
    } *start, *act;

int main(){

    freopen ("xormax.in","r",stdin);
    freopen ("xormax.out","w",stdout);

    scanf ("%d", &n  );
    start=new(bit);
    act=start;

    for ( j=30; j>=0; j-- ){
        if ( !act->it[biti[j]] )
            act->it[biti[j]]=new(bit);
        act=act->it[biti[j]];
    }
    for ( i=1; i<=n; i++ ){
        act=start;
        scanf ("%d", &nr );
        rez^=nr;
        nr=rez;
        for ( j=0; j<=30; j++ ){
            biti[j]=nr&1;
            nr>>=1;
        }

        // cautam opusul teoretic daca exista
        int find=0;
        act=start;
        for ( j=30; j>=0; j-- ){
//            printf("%d %d\n", act->it[0], act->it[1] );
            if ( act->it[biti[j]^1] ){
                act=act->it[biti[j]^1];
                find*=2;
                find+=biti[j]^1;
            }
            else{
                act=act->it[ biti[j] ];
                find*=2;
                find+=biti[j];
            }
        }
        if ( ( ( find ^ rez ) == maxim ) && ( dr-st > i-(act->val) ) ) {
            st=act->val;
            dr=i;            
        }
        if ( ( find ^ rez ) > maxim ){
            maxim=find^rez;
            st=act->val;
            dr=i;
        }
        // inseram
        act=start;
        for ( j=30; j>=0; j-- ){
            if ( !act->it[biti[j]] ){
                act->it[biti[j]]=new(bit);
            }
            act=act->it[biti[j]];
        }
        act->val=i;
    }
    printf("%d %d %d", maxim, st+1, dr );
    return 0;
}