Submission #498895

#	Time	Username	Problem	Language	Result	Execution time	Memory
498895		Gurban	XOR (IZhO12_xor)	C++17	100 / 100	146 ms	52692 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 = 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;
		add(nw,i);
		int ind = tap(nw);
		if(ans < i - ind){
			ans = i - ind;
			ii = ind + 1;
			k = i + 1 - ii;
		}
	}
	cout<<ii<<' '<<k;
}

• Subtask 1: 100 / 100