Cod sursa(job #2329704)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 27 ianuarie 2019 12:21:25
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("xormax.in");
ofstream g ("xormax.out");
struct gioto
{
    int st,dr,usu;
};
int nr,act,a,b,pup,n,x,sol,ant;
vector <gioto> v;
void update(int val,int bit,int nod,int poz)
{
    if(bit!=20) v[nod].usu=poz;
    if(bit==-1) return;
    if((1<<bit)&val)
    {
        if(!v[nod].dr)
        {
            ++nr;
            v[nod].dr=nr;
            v.push_back({0,0,0});
        }
        update(val,bit-1,v[nod].dr,poz);
    }
    if(!((1<<bit)&val))
    {
        if(!v[nod].st)
        {
            ++nr;
            v[nod].st=nr;
            v.push_back({0,0,0});
        }
        update(val,bit-1,v[nod].st,poz);
    }
}
void query(int val,int bit,int nod)
{
    if(bit==-1)
    {
        act=v[nod].usu;
        return;
    }
    if(v[nod].dr)
    {
        if(!((1<<bit)&val))
        {
            pup+=(1<<bit);
            query(val,bit-1,v[nod].dr);
        }
        else if(!v[nod].st) query(val,bit-1,v[nod].dr);
    }
    if(v[nod].st)
    {
        if((1<<bit)&val)
        {
            pup+=(1<<bit);
            query(val,bit-1,v[nod].st);
        }
        else if(!v[nod].dr) query(val,bit-1,v[nod].st);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    f>>n;
    v.push_back({0,0,0});
    for(int i=1;i<=n;++i)
    {
        f>>x;
        if(x>sol)
        {
            a=i;
            b=i;
            sol=x;
        }
        pup=0;
        x=ant^x;
        act=0;
        query(x,20,0);
        if(pup>sol)
        {
            sol=pup;
            b=i;
            a=act;
        }
        update(x,20,0,i);
        ant=x;
    }
    //for(int i=0;i<v.size();++i) g<<v[i].usu<<'\n';
    g<<sol<<' '<<a+1<<' '<<b;
    return 0;
}