Submission #498892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
498892	2021-12-26T14:10:40 Z	Gurban	XOR (IZhO12_xor)	C++17	0 / 100	19 ms	36732 KB

xor

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=3e5+5;
const int B = 31;
int n,x,sz = 1;
int dp[maxn * B];
int to[maxn * B][2];

void add(int v,int idx){
	int now = 0;
	dp[0] = min(dp[0],idx);
	for(int i = B-1;i >= 0;i--){
		int xx = (v >> i) & 1;
		if(!to[now][xx]) to[now][xx] = sz++;
		
		now = to[now][xx];
		dp[now] = min(dp[now],idx);
	}
}

int tap(int v){
	int now = 0;
	int cp = 1e9;
	bool tr = 1;
	for(int i = B-1;i >= 0;i--){
		int a = (v >> i) & 1;
		int b = (x >> i) & 1;
		if(!b and to[now][a ^ 1]) cp = min(cp,dp[to[now][a^1]]);
		
		if(to[now][a ^ b]) now = to[now][a^b];
		else {
			tr = 0;
			break;
		}
	}
	// if(tr) cp = min(cp,dp[now]);
	return cp;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> x;
	memset(dp, 127, sizeof dp);
	int nw = 0;
	int ans = 0;
	int ii = -1,k = -1;
	add(0,0);
	for(int i = 1;i <= n;i++){ 
		int a; cin >> a;
		nw ^= a;
		int ind = tap(nw);
		if(ans < i - ind){
			ii = ind + 1;
			k = i + 1 - ii;
		}
		add(nw,i);
	}
	cout<<ii<<' '<<k;
}

Compilation message

xor.cpp: In function 'int tap(int)':
xor.cpp:27:7: warning: variable 'tr' set but not used [-Wunused-but-set-variable]
   27 |  bool tr = 1;
      |       ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	36732 KB	Output is correct
2	Incorrect	16 ms	36640 KB	Output isn't correct
3	Halted	0 ms	0 KB	-