Cod sursa(job #1819612)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 30 noiembrie 2016 18:15:33
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Trie {
    Trie *n[2];
    int ind;

    Trie(){
        n[0]=n[1]=0;
        ind=0;
    }
};


void add(Trie *&t, int val, int poz, int ind){
    if(t==0) t = new Trie;

    if(poz<0){
        t->ind = max(t->ind,ind);
    }
    else{
        int dir = (val&(1<<poz))?1:0;
        add(t->n[dir],val,poz-1,ind);
    }
}

void findmax(Trie *&t, int val, int poz, int &omax, int &oind){
    if(poz<0){
        oind = t->ind;
    }
    else{
        int pref = 1 - ((val&(1<<poz))?1:0);
        if(t->n[pref]){
            omax |= (1<<poz);
            findmax(t->n[pref],val,poz-1,omax,oind);
        }
        else{
            findmax(t->n[1-pref],val,poz-1,omax,oind);
        }
    }


}

/*void showtrie(Trie *t, int nrs, int poz=20){
    if(poz>=0){
        if(t->n[0]){
            cout<<"0";
            showtrie(t->n[0],nrs+1,poz-1);
        }
        if(t->n[1]){
            cout<<string(nrs,'0')<<"1";
            showtrie(t->n[1],nrs+1,poz-1);
        }
    }
    else cout<<" = "<<t->ind <<'\n';
}*/



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

    int n; fin>>n;

    int mx=-1,start=0,stop=0;


    Trie *sumepart = 0;

    add(sumepart,0,20,0);
    /*cout<<"trie:\n";
    showtrie(sumepart,0);
    cout<<'\n';*/


    int xs=0;
    for(int i=1;i<=n;++i){
        int x; fin>>x;
        // do sth...
        //cout<<"read "<<x<<'\n';


        int curr=0,ind=0;
        xs = xs^x;
        findmax(sumepart, xs,20 ,curr,ind);
        //cout<<"got: "<<curr<<' '<<ind+1<<' '<<i<<'\n';
        if(curr>mx){mx=curr; start=ind+1; stop=i;}

        add(sumepart,xs,20,i);

        /*cout<<i<<" trie:\n";
        showtrie(sumepart,0);
        cout<<'\n';*/
    }
    fout<<mx<<' '<<start<<' '<<stop<<'\n';
}