Cod sursa(job #2807204)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 23 noiembrie 2021 16:10:06
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb

#include <bits/stdc++.h>
#define int long long
#define dim 100006
#define mod 666013//1000000007
using namespace std;
ifstream fin ("xormax.in");
ofstream fout("xormax.out");
int v[dim],p[25],ind,xo;
string s;

struct trie
{
    int last=0;
    trie *kids[2];
    trie ()
    {
        for (int i=0; i<2; i++)
            kids[i]=nullptr;
    }
};

trie* insert (trie *node,int index)
{
    if (node==nullptr)
        node=new trie;
    if (index<21)
        node->kids[s[index]-'0']=insert(node->kids[s[index]-'0'],index+1);
    else    node->last=ind;
    return node;
}

int bestpref(trie *node,int index)
{
    if (index==21)
        return node->last;
    else
    {
        if (node->kids[1-s[index]+'0']!=nullptr)
        {
            xo=xo^p[20-index]*(1-s[index]+'0');
            return bestpref(node->kids[1-s[index]+'0'],index+1);
        }
        else
        {
            xo=xo^p[20-index]*(s[index]-'0');
            return bestpref(node->kids[s[index]-'0'],index+1);
        }
    }
}

int32_t main()
{
    int n,i,j,solst,soldr,maxi=-1;
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>v[i];
        v[i]=(v[i]^v[i-1]);
    }
    p[0]=1;
    for (i=1; i<=20; i++)
        p[i]=2*p[i-1];
    trie *root=nullptr;
    for (i=1; i<=n; i++)
    {
        s.clear();
        xo=v[i];
        for (j=20; j>=0; j--)
            if ((v[i]&p[j])!=0)
                s+="1",v[i]-=p[j];
            else    s+="0";
        if (i>1)
        j=bestpref(root,0);
        else    j=0,xo=0;
        if (xo>maxi)
        {
            maxi=xo;
            solst=j,soldr=i;
        }
        ind=i;
        root=insert(root,0);
    }
    fout<<maxi<<' '<<solst+1<<' '<<soldr<<'\n';
    return 0;
}