답안 #340716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340716	2020-12-28T09:15:33 Z	juggernaut	XOR (IZhO12_xor)	C++14	100 / 100	212 ms	24428 KB

xor

#include<bits/stdc++.h>
using namespace std;
int par[250005],tree[250005*30][2],node,sub[250005*30],n,k;
void upd(int x){
	int now=0;
	for(int i=29;i>=0;i--){
		int bit=par[x]>>i&1;
		if(!tree[now][bit])
			tree[now][bit]=++node;
		now=tree[now][bit];
		sub[now]=max(sub[now],x);
	}
}
int get(int x){
	int now=0,val=0,res=0;
	for(int i=29;i>=0;i--){
		int bit=x>>i&1;
		int v1=tree[now][bit^1];
		int v0=tree[now][bit];
		if(v0&&v1){
			if(val+(1<<i)>=k)
				res=max(res,sub[v1]),now=v0;
			else
				val+=(1<<i),now=v1;
		}
		else if(v1){
			if(val+(1<<i)>=k)
				res=max(res,sub[v1]);
			else
				val+=(1<<i);
			now=v1;
		}
		else
			now=v0;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&par[i]);
		par[i]^=par[i-1];
	}
	int ans,mx=0;
	for(int i=n;i>=1;i--){
		upd(i);
		int res=get(par[i-1]);
		if(res&&res-i+1>=mx)mx=res-i+1,ans=i;
	}
	printf("%d %d",ans,mx);
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
xor.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |   scanf("%d",&par[i]);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	11 ms	1132 KB	Output is correct
6	Correct	18 ms	1132 KB	Output is correct
7	Correct	15 ms	1260 KB	Output is correct
8	Correct	18 ms	1260 KB	Output is correct
9	Correct	73 ms	11372 KB	Output is correct
10	Correct	72 ms	11500 KB	Output is correct
11	Correct	92 ms	11372 KB	Output is correct
12	Correct	77 ms	11372 KB	Output is correct
13	Correct	91 ms	11516 KB	Output is correct
14	Correct	75 ms	11500 KB	Output is correct
15	Correct	88 ms	11500 KB	Output is correct
16	Correct	100 ms	11372 KB	Output is correct
17	Correct	201 ms	24336 KB	Output is correct
18	Correct	199 ms	24300 KB	Output is correct
19	Correct	201 ms	24428 KB	Output is correct
20	Correct	212 ms	24428 KB	Output is correct