Cod sursa(job #2921890)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 2 septembrie 2022 12:33:27
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#import <algorithm>
#import <vector>
#import <map>
#import <set>
#import <deque>
#import <queue>
#import <cassert>
//#import <cmath>
#import <cstring>
#import <cctype>
#import <cstdlib>
#import <stack>
using namespace std;
struct nod
{
    int poz,val;
    nod*a[2];
    nod()
    {
        this->val=-1;
        this->poz=-1;
        a[0]=a[1]=nullptr;
    }
};
pair<int,int>caut(nod*&t,const int&s,const int& acm,int rez)
{
    if(acm==-1)
    {
        assert(t->val==rez);
        return make_pair(t->val,t->poz);
    }
    int c=((s>>acm)&1);
    rez*=2;
    if(t->a[c]==nullptr)
    {
        if(c==0)rez++;
        return caut(t->a[c^1],s,acm-1,rez);
    }
    else
    {
        rez+=c;
        return caut(t->a[c],s,acm-1,rez);
    }
}
void insert(nod*&t,const int&s,const int&poz,const int& acm,int rez)
{
    if(acm==-1)
    {
        assert(s==rez);
        t->poz=poz;
        t->val=s;
        return;
    }
    int c=((s>>acm)&1);
    rez*=2;
    rez+=c;
    if(t->a[c]==nullptr)
    {
        t->a[c]=new nod();
    }
    insert(t->a[c],s,poz,acm-1,rez);
}
main()
{
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    nod*S=new nod();
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    insert(S,0,0,20,0);
    int x=0,sol=-1,g,h,inv=(1<<21)-1;
    for(int i=1;i<=n;i++)
    {
        x^=a[i];
        pair<int,int>rez=caut(S,inv^x,20,0);
        insert(S,x,i,20,0);
        if(x^rez.first>sol)
        {
            sol=x^rez.first;
            g=rez.second+1;
            h=i;
        }
    }
    cout<<sol<<' '<<g<<' '<<h;
    delete S;
}