# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
90134 |
2018-12-20T14:12:50 Z |
Bodo171 |
XOR (IZhO12_xor) |
C++14 |
|
353 ms |
57012 KB |
#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;
}
# |
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 |