Cod sursa(job #3346592)

Utilizator And_etcAndrei P And_etc Data 14 martie 2026 14:15:49
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

using namespace std;

long long sp[100555];

vector <int> v[1000555];

int b[45];

int p[25];

int vl[1000555];

int iv[1000555];

int main()
{
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    int n,x,e1,e2;
    cin>>n;
    int ix=0;
    int mx=0;
    p[0]=1;
    for(int i=1;i<=21;++i)
    {
        p[i]=p[i-1]*2;
    }
        int nd=0;
        for(int h=21;h>=0;--h)
        {
            int ex=-1;
            for(auto a:v[nd])
            {
                if(vl[a]==b[h])
                {
                    ex=a;
                    break;
                }
            }
            if(ex==-1)
            {
                ++ix;
                vl[ix]=b[h];
                v[nd].push_back(ix);
                ex=ix;
            }
            nd=ex;
        }
    for(int i=1;i<=n;++i)
    {
        cin>>x;
        sp[i]=(sp[i-1]^x);
        int el=sp[i];
        int in=0;
        for(int h=0;h<=40;++h)
        {
            b[h]=0;
        }
        while(el)
        {
            if(el%2==1)
            {
                b[in]=1;
            }
            el/=2;
            ++in;
        }
        int nd=0;
        long long int nr=0;
        int s1=0;
        for(int h=21;h>=0;--h)
        {
            int ex=-1;
            for(auto a:v[nd])
            {
                if(vl[a]!=b[h])
                {
                    ex=a;
                    break;
                }
            }
            if(ex==-1)
            {
                ex=v[nd][0];
            }
            nd=ex;
            if(i==n)
            {
                //cout<<b[h]<<" "<<h<<"      "<<vl[nd]<<"\n";
            }
            if(vl[nd]!=b[h])
            {
                nr+=p[h];
            }
            s1=iv[nd];
        }
        if(nr>mx)
        {
            mx=nr;
            e1=s1+1;
            e2=i;
        }
        nd=0;
        for(int h=21;h>=0;--h)
        {
            int ex=-1;
            for(auto a:v[nd])
            {
                if(vl[a]==b[h])
                {
                    ex=a;
                    break;
                }
            }
            if(ex==-1)
            {
                ++ix;
                vl[ix]=b[h];
                v[nd].push_back(ix);
                ex=ix;
            }
            nd=ex;
            iv[nd]=i;
        }

    }
    cout<<mx<<" "<<e1<<" "<<e2;;
    return 0;
}