Cod sursa(job #2120811)

Utilizator mihnea00Duican Mihnea mihnea00 Data 2 februarie 2018 21:42:30
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 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,panala,idx,nivel,poz,frm,too,Max,v[100010];
bool ok;

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

vector<crengutze> l;


void add(int x)
{
    nivel=0;

    int putere2=22;
    bool bit;

    while(putere2>=0)
    {
        bit=x&(1<<putere2);

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

        if(putere2==0)
        {
            l[nivel].poz=i;
            //fout<<i<<"\n";
        }

        --putere2;
    }
}

int srch_the_copac(int x)
{
    nivel=0;

    int putere2=22;
    bool bit;

    while(putere2>=0)
    {
        bit=x&(1<<putere2);

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

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

        --putere2;
    }
}

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

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

        poz=srch_the_copac(v[i]);

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

        add(v[i]);
    }

    fout<<Max<<" "<<dela<<" "<<panala;

    return 0;
}