Submission #90134

#	Time	Username	Problem	Language	Result	Execution time	Memory
90134		Bodo171	XOR (IZhO12_xor)	C++14	100 / 100	353 ms	57012 KiB

xor

#include <iostream>
#include <fstream>
using namespace std;
int n,sum,x,i,j,p,wh,pos,k,mx,poz;
struct Trie
{
    Trie *son[2];
    int ap;
    Trie()
    {
        son[0]=son[1]=0;
        ap=n+1;
    }
}*rad=new Trie;
void ins(int val)
{
    Trie *nod=rad;
    for(p=30;p>=0;p--)
    {
        wh=((val>>p)&1);
        if(!nod->son[wh])
          nod->son[wh]=new Trie;
        nod=nod->son[wh];
        if(i<nod->ap)
            nod->ap=i;
    }
}
void query(int val)
{
    Trie *nod=rad;
    for(p=30;p>=0;p--)
    {
        wh=((val>>p)&1);
        pos=((k>>p)&1);
        if(!pos)
        {
            if(nod->son[1-wh]&&i-nod->son[1-wh]->ap>mx)
            {
                mx=i-nod->son[1-wh]->ap;
                poz=i;
            }
        }
        if(!nod->son[(wh^pos)])
            return;
        nod=nod->son[(wh^pos)];
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>k;k--;
    ins(0);
    for(i=1;i<=n;i++)
    {
        cin>>x;
        sum^=x;
        ins(sum);
        query(sum);
    }
    cout<<poz-mx+1<<' '<<mx;
    return 0;
}

• Subtask 1: 100 / 100