제출 #1357086

#제출 시각아이디문제언어결과실행 시간메모리
1357086CutSandstoneXOR (IZhO12_xor)C++20
100 / 100
63 ms21464 KiB
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;
using ll = long long;
const ll oo = 1e18;
const int N = 25e4, LG = 31;
int trie[N * LG][2];
int val[N * LG];
int pt = 1;
void add(int x, int v) {
	int p = 0;
	for (int i = LG - 1; i >= 0; i--) {
		bool b = (x >> i) & 1;
		if (trie[p][b] == -1) {
			trie[pt][0] = trie[pt][1] = -1;
			val[pt] = v;
			trie[p][b] = pt++;
		}
		p = trie[p][b];
		val[p] = min(val[p], v);
	}
}
int query(int x, int k) {
	int p = 0;
	int ans = INT_MAX >> 1;
	for (int i = LG - 1; i >= 0 && p != -1; i--) {
		bool b = (x >> i) & 1;
		if ((k >> i) & 1)
			b = !b;
		else if (trie[p][!b] != -1)
			ans = min(ans, val[trie[p][!b]]);
		p = trie[p][b];
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	trie[0][0] = trie[0][1] = -1;
	add(0, -1);
	int v = 0;
	int n, x;
	cin >> n >> x;
	x--;
	int r = -1, len = -1;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int c;
		cin >> c;
		v ^= c;
		add(v, i);
		int cur = query(v, x);
		if (i - cur > len) {
			len = i - cur;
			r = cur + 1;
		}
	}
	assert(r != -1);
	cout << r + 1 << " " << len << "\n";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…