Cod sursa(job #3230792)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 22 mai 2024 20:22:58
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 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,x;

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)
    {
        int bit=0;
        if ((x&p[20-index])!=0)
            bit=1;
        node->kids[bit]=insert(node->kids[bit],index+1);
    }
    else    node->last=ind;
    return node;
}

int bestpref(trie *node,int index)
{
    if (index==21)
        return node->last;
    else
    {
        int bit=0;
        if ((x&p[20-index])!=0)
            bit=1;
        if (node->kids[bit]!=nullptr)
            bit=1-bit;
        xo=xo^p[20-index]*bit;
        return bestpref(node->kids[bit],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;
    root=insert(root,0);
    for (i=1; i<=n; i++)
    {
        x=v[i];
        xo=v[i];
        j=bestpref(root,0);
        if (xo>maxi)
        {
            maxi=xo;
            solst=j,soldr=i;
        }
        ind=i;
        root=insert(root,0);
    }
    fout<<maxi<<' '<<solst+1<<' '<<soldr<<'\n';
    return 0;
}