제출 #1101245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101245		muntasir__	XOR (IZhO12_xor)	C++17	100 / 100	92 ms	93260 KiB

xor

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const ll mod = 1e9 + 7;
const int MX = 31 * 250005;

int num, B = 30;
int cnt[MX], trie[MX][2];

void init() {
	num = 0;
	for (int i = 0; i < MX; i++)cnt[i] = INT32_MAX;
	memset(trie, -1, sizeof(trie));
}
void insert(int node, int val, int i, int idx) {
	if (i == -1) {
		cnt[node] = min(cnt[node], idx);
		return;
	}
	int k = val >> i & 1;
	if (trie[node][k] == -1)trie[node][k] = ++num;
	int child = trie[node][k];
	insert(child, val, i - 1, idx);
	cnt[node] = min(cnt[node], cnt[child]);
}
int query(int node, int i, int val, int k) {
	if (i == -1) {
		return cnt[node];
	}
	int b1 = k >> i & 1;
	int b2 = val >> i & 1;
	int ans = INT32_MAX;
	if (b1) {
		int child = trie[node][!b2];
		if (child != -1)ans = query(child, i - 1, val, k);
	} else {
		int c1 = trie[node][!b2], c2 = trie[node][b2];
		if (c1 != -1)ans = min(ans, query(c1, i - 1, val, k));
		if (c2 != -1)ans = min(ans, query(c2, i - 1, val, k));
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, x;
	cin >> n >> x;
	int cur = 0;
	init();
	insert(0, cur, B, 0);
	int idx = 1, k = 0;
	for (int i = 1; i <= n; i++) {
		int y;
		cin >> y;
		cur ^= y;
		int val = query(0, B, cur, x);
		if (val != INT32_MAX) {
			int dis = (i - val);
			if (dis > k) {
				k = dis;
				idx = val + 1;
			}
		}
		insert(0, cur, B, i);
	}
	cout << idx << " " << k << "\n";
}

• Subtask 1: 100 / 100