답안 #902509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902509	2024-01-10T14:00:34 Z	LCJLY	XOR (IZhO12_xor)	C++14	100 / 100	324 ms	116660 KB

xor

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

struct trie{
	trie *next[2];
	int left=INT_MAX;
	
	trie(){
		next[0]=next[1]=NULL;
	}
};

auto root=new trie();
	
void solve(){	
	int n,k;
	cin >> n >> k;
	
	int arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	int hold=0;
	int best=-1;
	int index=-1;
	auto cur2=root;
	for(int x=30;x>=0;x--){
		if(cur2->next[0]==NULL) cur2->next[0]=new trie();
		cur2=cur2->next[0];
		cur2->left=-1;
	}
	for(int x=0;x<n;x++){
		hold^=arr[x];
		auto cur=root;
		//query
		for(int y=30;y>=0;y--){
			if(k&(1<<y)){
				bool amos=(hold&(1<<y));
				amos^=1;
				//cout << amos;
				if(cur->next[amos]==NULL)cur->next[amos]=new trie();
				cur=cur->next[amos];
			}
			else{
				bool amos=(hold&(1<<y));
				//cout << amos;
				if(cur->next[amos]==NULL)cur->next[amos]=new trie();
				if(cur->next[!amos]!=NULL){
					int cnt=x-cur->next[!amos]->left;
					if(cnt>best){
						best=cnt;
						index=x+1;
					}
				}
				cur=cur->next[amos];
			}
		}
		
		//cout << endl;
		//show(best,best);
		if(x-cur->left>best){
			best=x-cur->left;
			index=x+1;
		}
		
		//add
		cur=root;
		for(int y=30;y>=0;y--){
			bool amos=(hold&(1<<y));
			if(cur->next[amos]==NULL)cur->next[amos]=new trie();
			cur=cur->next[amos];
			cur->left=min(cur->left,x);
		}
		//show(best2,best);
	}
	
	cout << index-best+1 << " " << best;
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}


 

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	12 ms	3448 KB	Output is correct
6	Correct	10 ms	3680 KB	Output is correct
7	Correct	10 ms	3772 KB	Output is correct
8	Correct	12 ms	3976 KB	Output is correct
9	Correct	100 ms	54800 KB	Output is correct
10	Correct	114 ms	55136 KB	Output is correct
11	Correct	103 ms	54616 KB	Output is correct
12	Correct	143 ms	54900 KB	Output is correct
13	Correct	119 ms	54840 KB	Output is correct
14	Correct	144 ms	54972 KB	Output is correct
15	Correct	101 ms	54848 KB	Output is correct
16	Correct	116 ms	54868 KB	Output is correct
17	Correct	294 ms	116604 KB	Output is correct
18	Correct	298 ms	116568 KB	Output is correct
19	Correct	324 ms	116660 KB	Output is correct
20	Correct	269 ms	116560 KB	Output is correct