Cod sursa(job #2534568)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 30 ianuarie 2020 18:51:42
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>
#define _2la20 (1<<20)
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int nrformat,bit,n,i,putere,ps,x,val[100003];
int aux,maxx;
pair<int,int> sol;
struct trie
{
    trie *f[2];
    int val;
    trie()
    {
        f[0]=f[1]=NULL;
    }
};
int bt(trie *r)
{
/// ps este numarul
/// putere este bitul pe care il verific
/// daca este 0 ma duc opus
    if(putere==0)
    {
        return r->val;
    }
    bit=1;
    if((putere&ps))
        bit=0;
    putere>>=1;
    if(!r->f[bit])
        bit=1-bit;
    return bt(r->f[bit]);
}
void adaug(trie *r)
{
    if(putere)
    {
        bit=0;
        if((putere&ps))
            bit=1;
        putere>>=1;
        if(!r->f[bit])
        {
            r->f[bit]= new trie;
        }
        adaug(r->f[bit]);
    }
    else {
        r->val=i;
    }
}
int main()
{
    trie *rad=new trie;
    fin>>n;
    putere=_2la20;
    adaug(rad); ///adun 0 la trie
    for(i=1; i<=n; i++)
    {
        fin>>x;
        ps^=x;
        val[i]=ps;
        putere=_2la20;
        aux=bt(rad);
      //  cout<<aux<<" "<<(val[aux]^ps)<<endl;
        if((val[aux]^ps)>maxx){
            maxx=(val[aux]^ps);
            sol.first=aux+1;
            sol.second=i;
        }
        putere=_2la20;
        adaug(rad);
    }
    fout<<maxx<<" "<<sol.first<<" "<<sol.second;
}