Submission #90134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90134	2018-12-20T14:12:50 Z	Bodo171	XOR (IZhO12_xor)	C++14	100 / 100	353 ms	57012 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	500 KB	Output is correct
3	Correct	2 ms	580 KB	Output is correct
4	Correct	3 ms	660 KB	Output is correct
5	Correct	15 ms	1848 KB	Output is correct
6	Correct	18 ms	1992 KB	Output is correct
7	Correct	20 ms	2004 KB	Output is correct
8	Correct	21 ms	2136 KB	Output is correct
9	Correct	136 ms	26964 KB	Output is correct
10	Correct	127 ms	27028 KB	Output is correct
11	Correct	125 ms	27028 KB	Output is correct
12	Correct	129 ms	27052 KB	Output is correct
13	Correct	129 ms	27072 KB	Output is correct
14	Correct	120 ms	27116 KB	Output is correct
15	Correct	127 ms	27116 KB	Output is correct
16	Correct	124 ms	27116 KB	Output is correct
17	Correct	340 ms	56712 KB	Output is correct
18	Correct	332 ms	56804 KB	Output is correct
19	Correct	333 ms	57012 KB	Output is correct
20	Correct	353 ms	57012 KB	Output is correct