제출 #1327066

#제출 시각아이디문제언어결과실행 시간메모리
1327066goats_9XOR (IZhO12_xor)C++20
100 / 100
288 ms113756 KiB
/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Trie {
	enum { K = 2, D = 30 };
	struct Node {
		vector<int> nxt = vector<int> (K, -1);
		int ts = 0;
	};
	vector<Node> tr;
	Trie() : tr(1, Node()) {}
	void add(int x, int t) {
		int cur = 0;
		for (int j = D - 1; j >= 0; j--) {
			int b = x >> j & 1;
			if (tr[cur].nxt[b] == -1) {
				tr[cur].nxt[b] = (int)tr.size();
				tr.push_back(Node());
			}
			cur = tr[cur].nxt[b];
			tr[cur].ts = max(t, tr[cur].ts);
		}
	}
	int query(int x, int l) {
		int r = -1, cur = 0;
		for (int j = D - 1; j >= 0; j--) {
			int z = x >> j & 1;
			int b = l >> j & 1;
			z ^= 1;
			if (tr[cur].nxt[z] == -1) {
				z ^= 1;
				if (b) return r;
			} else {
				if (!b) {
					r = max(r, tr[tr[cur].nxt[z]].ts);
					z ^= 1;
					if (tr[cur].nxt[z] == -1) return r;
				}
			}
			cur = tr[cur].nxt[z];
		}
		return max(r, tr[cur].ts);
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (auto& u : a) cin >> u;
	int z = 0;
	Trie trie;
	trie.add(0, n);
	int j = n - 1, k = 0;
	for (int i = n - 1; i >= 0; i--) {
		z ^= a[i];
		trie.add(z, i);
		int u = trie.query(z, x);
		if (u - i >= k) j = i, k = u - i;
	}
	cout << j + 1 << ' ' << k;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...