Cod sursa(job #2921934)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 2 septembrie 2022 14:21:30
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 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];
};
pair<int,int>caut(nod*t,const int s,const int acm)
{
    if(acm==-1)
    {
        auto rez=make_pair(t->val,t->poz);
        return rez;
    }
    int c=(s&(1<<acm))!=0;
    if(t->a[c]==nullptr)
    {
        c^=1;
    }
    return caut(t->a[c],s,acm-1);
}
void insert(nod*&t,const int s,const int&poz,const int acm)
{
    if(acm==-1)
    {
        t->poz=poz;
        t->val=s;
        return;
    }
    int c=(s&(1<<acm))!=0;
    if(t->a[c]==nullptr)
    {
        t->a[c]=new nod();
    }
    insert(t->a[c],s,poz,acm-1);
}
main()
{
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    nod*S=new nod();
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    int x=0,rez=-1,g,h;const int inf=(1<<21)-1;
    for(int i=1;i<=n;i++)cin>>a[i];
    insert(S,0,0,20);
    for(int i=1;i<=n;i++)
    {
        x^=a[i];
        int y=x^inf;
        pair<int,int> sol=caut(S,y,20);
        if(rez<(sol.first^x))
        {
            rez=sol.first^x;
            g=sol.second+1;
            h=i;
        }
        insert(S,x,i,20);
    }
    cout<<rez<<' '<<g<<' '<<h;
}