Submission #321193

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321193	2020-11-11T12:57:56 Z	kshitij_sodani	XOR (IZhO12_xor)	C++14	100 / 100	1834 ms	19904 KB

xor

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n,x;
llo it[300001];
pair<llo,llo> ans={-1,-1};
void re(llo i,llo j){
	if(j>ans.b){
		ans={i,j};
	}
	else if(j==ans.b and i<ans.a){
		ans={i,j};
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>x;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	if(x==0){
		cout<<1<<" "<<n<<endl;
		return 0;
	}
	vector<pair<llo,llo>> val;
	for(llo i=0;i<30;i++){
		if((1LL<<i)>=x){
			val.pb({1LL<<i,1LL<<i});
		}
	}
	vector<llo> xx;
	for(llo i=29;i>=0;i--){
		if(x&(1LL<<i)){
			xx.pb(1);
		}
		else{
			xx.pb(0);
		}
	}
	reverse(xx.begin(),xx.end());
	while(xx.size()){
		if(xx.back()==0){
			xx.pop_back();
		}
		else{
			break;
		}
	}
	
	val.pb({((1LL<<xx.size()))-1,x});
	for(llo i=xx.size();i>0;i--){
		llo cur=0;
		llo cur2=0;
		if(xx[i-1]==1){
			continue;
		}
		llo yy=xx.size();
		for(llo j=i;j<xx.size();j++){
			cur+=(1LL<<j);
			cur2+=(x&(1LL<<j));
		}
		cur+=(1LL<<(i-1));
		cur2+=(1LL<<(i-1));
		val.pb({cur,cur2});
	}
	for(auto j:val){
		map<llo,llo> cc;
		cc[0]=0;
		llo cur=-1;
		for(llo i=0;i<n;i++){
			cur^=(it[i]&j.a);
			if(cc.find(cur^j.b)!=cc.end()){
				llo x=cc[cur^j.b];
				re(x+1,i-x);
			}
			if(cc.find(cur)==cc.end()){
				cc[cur]=i;
			}

		}
	}
/*	for(auto j:val){
		cout<<j.a<<','<<j.b<<endl;
	}*/
	cout<<ans.a+1<<" "<<ans.b<<endl;









 
 
	return 0;
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:66:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(llo j=i;j<xx.size();j++){
      |               ~^~~~~~~~~~
xor.cpp:65:7: warning: unused variable 'yy' [-Wunused-variable]
   65 |   llo yy=xx.size();
      |       ^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	396 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	10 ms	1644 KB	Output is correct
6	Correct	22 ms	1900 KB	Output is correct
7	Correct	13 ms	2028 KB	Output is correct
8	Correct	14 ms	2156 KB	Output is correct
9	Correct	333 ms	8144 KB	Output is correct
10	Correct	336 ms	8312 KB	Output is correct
11	Correct	291 ms	8164 KB	Output is correct
12	Correct	273 ms	8036 KB	Output is correct
13	Correct	210 ms	8292 KB	Output is correct
14	Correct	248 ms	8164 KB	Output is correct
15	Correct	475 ms	8164 KB	Output is correct
16	Correct	232 ms	8168 KB	Output is correct
17	Correct	1550 ms	19832 KB	Output is correct
18	Correct	1328 ms	19812 KB	Output is correct
19	Correct	1834 ms	19904 KB	Output is correct
20	Correct	1022 ms	19812 KB	Output is correct