Submission #106707

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106707	2019-04-19T18:43:45 Z	Pajaraja	XOR (IZhO12_xor)	C++17	100 / 100	247 ms	23420 KB

xor

#include <bits/stdc++.h>
#define MAXN 250007
using namespace std;
int t,sn[2][30*MAXN],mn[30*MAXN],x,n,arr[MAXN];
void ubaci(int s,int d,int b,int ind)
{
	if(d==-1) return;
	int z=((1<<d)&b)>>d;
	if(!sn[z][s]) {sn[z][s]=++t; mn[sn[z][s]]=ind;}
	ubaci(sn[z][s],d-1,b,ind);
}
int poredi(int s,int d,int b)
{
	if(d==-1) return mn[s];
	int z=((1<<d)&b)>>d,sol=MAXN;
	if(!(x&(1<<d)) && sn[1-z][s]) sol=mn[sn[1-z][s]];
	if(sn[z][s]) sol=min(sol,poredi(sn[z][s],d-1,b));
	return sol; 
}
int main()
{
	scanf("%d%d",&n,&x);
	int mx=0,mnd,tr=0;
	ubaci(0,29,0,0);
	for(int i=1;i<=n;i++)
	{
		int np;
		scanf("%d",&np); tr^=np;
		int kn=i-poredi(0,29,tr^x);
		if(kn>mx) {mx=kn; mnd=i-kn+1;}
		ubaci(0,29,tr,i);
	}
	printf("%d %d",mnd,mx);
	
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&x);
  ~~~~~^~~~~~~~~~~~~~
xor.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&np); tr^=np;
   ~~~~~^~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	12 ms	1024 KB	Output is correct
6	Correct	12 ms	1024 KB	Output is correct
7	Correct	12 ms	1152 KB	Output is correct
8	Correct	13 ms	1152 KB	Output is correct
9	Correct	89 ms	11128 KB	Output is correct
10	Correct	69 ms	11100 KB	Output is correct
11	Correct	64 ms	11128 KB	Output is correct
12	Correct	75 ms	11000 KB	Output is correct
13	Correct	68 ms	11064 KB	Output is correct
14	Correct	76 ms	11128 KB	Output is correct
15	Correct	63 ms	11128 KB	Output is correct
16	Correct	79 ms	11128 KB	Output is correct
17	Correct	193 ms	23304 KB	Output is correct
18	Correct	185 ms	23288 KB	Output is correct
19	Correct	247 ms	23364 KB	Output is correct
20	Correct	232 ms	23420 KB	Output is correct