Cod sursa(job #2329680)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 27 ianuarie 2019 11:50:23
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 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) return;
    if(bit!=21) v[nod].usu=poz;
    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) return;
    if(bit!=21) act=max(act,v[nod].usu);
    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;
    f>>x;
    v.push_back({0,0,0});
    for(int i=1;i<=n;++i)
    {
        if(x>sol)
        {
            a=i;
            b=i;
            sol=x;
        }
        f>>x;
        pup=0;
        x=ant^x;
        act=0;
        query(x,21,0);
        if(pup>sol)
        {
            sol=pup;
            b=i;
            a=act;
        }
        update(x,21,0,i);
        ant=x;
    }
    g<<sol<<' '<<a+1<<' '<<b+1;
    return 0;
}