Cod sursa(job #3209277)

Utilizator matei__bBenchea Matei matei__b Data 2 martie 2024 11:21:42
Problema Xor Max Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 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"); 

bool curr[dim];

struct trie 
{
    struct nod 
    {
        vector<int> pos;
        nod *st;
        nod *dr; // merg in stanga cu 1 si in dreapta cu 0

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

    nod *rad=new nod;

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

        for(int i=29; i>=0; i--)
        {
            if(x&(1<<i))
            {
                //cout << 1;
                if(aux->st==nullptr)
                {
                    aux->st=new nod;
                    aux=aux->st;
                }
                else 
                {
                    aux=aux->st;
                }
            }
            else 
            {
                //cout << 0;
                if(aux->dr==nullptr)
                {
                    aux->dr=new nod;
                    aux=aux->dr;
                }
                else 
                {
                    aux=aux->dr;
                }
            }

            if(i==0)
                aux->pos.pb(ind);
        }
    }

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

        int ans=0;

        for(int i=29; 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)
            {
                int mx=0;

                for(auto it:aux->pos)
                    mx=max(mx,it);
                
                return mp(ans,mx);
            }
        }
    }
}v;

int n;
int a[dim];
int sp;

int mx,st=1,dr=1;

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

    fin >> n;

    v.insert(0,1);

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

        sp=(sp^a[i]);

        v.insert(sp,i+1);

        pii u=v.cauta(sp);

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

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

    return 0;
}