Cod sursa(job #2120665)

Utilizator mihnea00Duican Mihnea mihnea00 Data 2 februarie 2018 19:07:11
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <iostream>
#include <vector>


using namespace std;

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

int a,b,c=0,n,i,x,dela,idx,nivel,poz,frm,too,Max,v[100010];
bool ok;

/*struct partiale
{
    int poz,suma;
} v[100010];*/


struct crengutze
{
    int catre[3],poz;
} continut;

vector<crengutze> l;

void add_in_trie(bool bit)
{

        if(l[nivel].catre[bit]==0)
        {
            ++idx;
            l.push_back({});
            l[nivel].catre[bit]=idx;
        }
        nivel=l[nivel].catre[bit];

    if(ok==1)
    {
        //fout<<nivel<<"\n";
        l[nivel].poz=dela;
    }
}

/*int baza2srch(int nivel,int puterede2,int x)
{
    if(puterede2==-1)
    {
        return l[nivel].poz;
    }

    bool bit=( x&(1<<puterede2) );

    if(l[nivel].catre[!bit]!=0)
    {
            baza2srch(l[nivel].catre[!bit],puterede2-1,x);
    }
    baza2srch(l[nivel].catre[bit],puterede2-1,x);
}*/

int srch(int x)
{
    nivel=0;
    bool bit;
    int puterede2=21;
    while(puterede2>=0)
    {
        bit=(x & (1 << puterede2));

        if( l[nivel].catre[!bit]!=0 )
            nivel=l[nivel].catre[!bit];
        else
            nivel=l[nivel].catre[bit];

        if(puterede2==0)
        {
            return l[nivel].poz;
        }
        --puterede2;
    }

}

void baza2add(int x)
{
    nivel=0;
    bool bit;
    int puterede2=21;
    while(puterede2>=0)
    {
        bit=(x & (1 << puterede2));

        if(puterede2==0)
        {
            ok=1;
            dela=i;
        }

        add_in_trie(bit);

        --puterede2;
    }
    /*nivel=0;
    while(x)
    {
        bool bit=x%2;
        x/=2;
        //fout<<bit;
        if(x==0)
        {
            ok=1;
            dela=i;
        }
        add_in_trie(bit);
    }
    //fout<<"\n";*/
}

int main()
{
    fin>>n;
    l.push_back({});

    for(i=1;i<=n;++i)
    {
        fin>>x;
        ok=0;
        v[i]=v[i-1]^x;

        //poz=baza2srch(0,21,v[i].suma);
        poz=srch(v[i]);

        if((v[poz]^v[i])>Max);
        {
            Max=v[poz]^v[i];
            frm=poz+1;
            too=i;
        }

        baza2add(v[i]);
    }

    fout<<Max<<" "<<frm<<" "<<too;
    /*bool kadi;
    kadi=19&32;
    cout<<kadi;*/
    //fout<<idx;


        //fout<<v[i].suma<<"\n";

    /*for(i=4;i<=6;++i)
    {
        c=c^v[i].x;
    }
    a=14^1;
    fout<<c<<" "<<a;*/


    return 0;
}