Submission #321194

#	Time	Username	Problem	Language	Result	Execution time	Memory
321194		kshitij_sodani	XOR (IZhO12_xor)	C++14	100 / 100	708 ms	13764 KiB

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){
		unordered_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 (stderr)

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 / 100