Cod sursa(job #3209336)

Utilizator matei__bBenchea Matei matei__b Data 2 martie 2024 11:35:09
Problema Xor Max Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define chad char
#define mod 1'000'000'009
#define dim 100005
#define lim 1000000
#define INF 1000000000
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define piii pair<int,pair<int,int> > 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define nr_biti __builtin_popcount
using namespace std;
 
ifstream fin("xormax.in");    
ofstream fout("xormax.out"); 

struct trie 
{
    struct nod 
    {
        int pos;
        nod *st;
        nod *dr;

        nod()
        {
            pos=0;
            st=dr=nullptr;
        }
    };

    nod *rad=new nod;

    void insert(const int &x,const int &ind)
    {
        nod *aux=rad;

        for(int i=21; i>=0; i--)
        {
            if(x&(1<<i))
            {
                if(aux->st==nullptr)
                    aux->st=new nod;

                aux=aux->st;
            }
            else 
            {
                if(aux->dr==nullptr)
                    aux->dr=new nod;

                aux=aux->dr;
            }

            if(!i)
                aux->pos=ind;
        }
    }

    pii cauta(const int &x)
    {
        nod *aux=rad;

        int ans=0;

        for(int i=21; i>=0; i--)
        {
            if(x&(1<<i))
            {
                if(aux->dr!=nullptr)
                {
                    ans|=(1<<i);
                    aux=aux->dr;
                }
                else 
                    aux=aux->st;
            }
            else 
            {
                if(aux->st!=nullptr)
                {
                    ans|=(1<<i);
                    aux=aux->st;
                }
                else 
                    aux=aux->dr;
            }

            if(i==0)
                return mp(ans,aux->pos);
        }

        return mp(0,0);
    }

}v;

int n;
int a[dim],sp[dim];
int mx,st=1,dr=1;

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr); 

    fin >> n;

    for(int i=1; i<=n; i++)
    {
        fin >> a[i];

        sp[i]=(sp[i-1]^a[i]);
    }

    for(int i=1; i<=n; i++)
    {
        v.insert(sp[i-1],i);

        pii u=v.cauta(sp[i]);

        if(u.first>mx)
        {
            mx=u.first;
            st=u.second;
            dr=i;
        }
        else if(u.first==mx && i-u.second<dr-st)
        {
            mx=u.first;
            st=u.second;
            dr=i;
        }
    }

    fout << mx << " " << st << " " << dr;

    return 0;
}