Submission #547689

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547689	2022-04-11T12:55:58 Z	nishkarsh	XOR (IZhO12_xor)	C++14	100 / 100	255 ms	25308 KB

xor

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 3e5+10;
const int mod = 1e9+7;
const int bits = 31;
int trie[bits*upperlimit][2];
int mxind[bits*upperlimit];
int prefxor[upperlimit];
int a[upperlimit];
int bin_rep[bits];
int bin_rep_target[bits];
int node_cnt=0,target;
void addnum(int x,int ind){
	for(int i = 0; i < bits; i++){
		bin_rep[i]=x&1;
		x>>=1;
	}
	int node = 0;
	for(int i = bits-1; i >= 0; i--){
		if(! trie[node][bin_rep[i]]) trie[node][bin_rep[i]]=++node_cnt;
		node=trie[node][bin_rep[i]];
		mxind[node]=max(mxind[node],ind);
	}
}
int query(int x){
	for(int i = 0; i < bits; i++){
		bin_rep[i]=x&1;
		x>>=1;
	}
	int ans = 0;
	int node = 0;
	for(int i = bits-1; i >= 0; i--){
		if(bin_rep_target[i]){
			if(! trie[node][1^bin_rep[i]]) return ans;
			else node = trie[node][1^bin_rep[i]];
		}
		else{
			ans=max(ans,mxind[trie[node][1^bin_rep[i]]]);
			if(! trie[node][bin_rep[i]]) return ans;
			else node = trie[node][bin_rep[i]];
		}
	}
	ans=max(ans,mxind[node]);
	return ans;
}
int main(){
	int n;
	cin >> n >> target;
	for(int j = 1; j <= n; j++){
		cin >> a[j];
		prefxor[j]=prefxor[j-1]^a[j];
	}
	int temp=target;
	for(int i = 0; i < bits; i++){
		bin_rep_target[i]=temp&1;
		temp>>=1;
	}
	int i,k=0,suffxor = 0;
	for(int j = n; j > 0; j--){
		addnum(suffxor,j);
		int x = query(prefxor[n]^prefxor[j-1]);
		suffxor^=a[j];
		if((x)&&(x+1-j >= k)){
			i=j;
			k=x+1-j;
		}
	}
	cout << i << " " << k;
	return 0;
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:103:15: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |  cout << i << " " << k;
      |               ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	15 ms	1148 KB	Output is correct
6	Correct	18 ms	1176 KB	Output is correct
7	Correct	19 ms	1252 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	69 ms	11676 KB	Output is correct
10	Correct	89 ms	11812 KB	Output is correct
11	Correct	79 ms	11744 KB	Output is correct
12	Correct	75 ms	11756 KB	Output is correct
13	Correct	68 ms	11824 KB	Output is correct
14	Correct	75 ms	11772 KB	Output is correct
15	Correct	84 ms	11712 KB	Output is correct
16	Correct	74 ms	11796 KB	Output is correct
17	Correct	199 ms	25144 KB	Output is correct
18	Correct	210 ms	25248 KB	Output is correct
19	Correct	206 ms	25228 KB	Output is correct
20	Correct	255 ms	25308 KB	Output is correct