Submission #1326978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326978		goats_9	XOR (IZhO12_xor)	C++20	0 / 100	1 ms	332 KiB

xor

/* 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 ans = -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 ans;
			} else {
				if (!b) {
					ans = max(ans, tr[tr[cur].nxt[z]].ts);
					z ^= 1;
					if (tr[cur].nxt[z] == -1) return ans;
				}
			}
			cur = tr[cur].nxt[z];
		}
		ans = max(ans, tr[cur].ts);
		return ans;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	freopen("c.out", "w", stdout);
	freopen("c.in", "r", stdin);
	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, 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;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("c.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xor.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("c.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100