Submission #498879

#	Time	Username	Problem	Language	Result	Execution time	Memory
498879		Gurban	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	332 KiB

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 = 1;
	dp[1] = min(dp[1],idx);
	for(int i = B-1;i >= 0;i--){
		int xx = (v >> i) & 1;
		if(!to[now][xx]) to[now][xx] = ++sz;
		
		dp[to[now][xx]] = min(dp[to[now][xx]],idx);
		now = to[now][xx];
	}
}

int tap(int v){
	int now = 1;
	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;
	for(int i = 1;i <= n * B;i++) dp[i] = 1e9;
	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;
}

• Subtask 1: 0 / 100