Submission #1112022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112022		Tsagana	XOR (IZhO12_xor)	C++14	100 / 100	82 ms	25264 KiB

xor

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int ans[2];
int dp[250000];
int M[7750620];
int T[7750620][2];

void solve () {
	int n, s; cin >> n >> s;
	
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		dp[i] = dp[i-1]^x;
	}

	int l = 0;
	for (int i = 0; i <= n; i++) {
		int x = 0;

		for (int j = 30; j >= 0; j--) {
			int id = (dp[i] & 1<<j) ? 1 : 0;
			
			if (!T[x][id]) T[x][id] = ++l;
			x = T[x][id];
			M[x] = i;
		}
	}
	
	for (int i = 0; i < n; i++) {
		int x = 0, mx = 0;

		for (int j = 30; j >= 0; j--) {
			int a = (s & 1<<j);
			int id = (a^(dp[i] & 1<<j) ? 1 : 0);

			if (!a) mx = max(mx, M[T[x][!id]]);
			if (!(x = T[x][id])) break;
		}
		mx = max(mx, M[x]);
		if (ans[1] < mx-i) ans[1] = mx-i, ans[0] = i+1;
	}
	cout << ans[0] << ' ' << ans[1] << '\n';
}
int main() {IOS solve(); return 0;}

• Subtask 1: 100 / 100