Submission #1248501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248501		xydwe12312	XOR (IZhO12_xor)	C++20	0 / 100	2095 ms	58448 KiB

xor

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

#define int long long
#define ll long long

const int mod = 1000000007; // 998244353;
const int N = 2e5 + 5;

struct Node {

	Node *links[2];
	int prefix;

	Node *getKey(int bit) {
		return links[bit];
	}

	bool containsKey(int bit) {
		return (links[bit] != NULL);
	}

	void createTrie(int bit, Node *node) {
		links[bit] = node;
	}

	void inc(Node *node) {
		node->prefix++;
	}

	void dec(Node *node) {
		node->prefix--;
	}
};

class Trie
{
private:
	Node *root;

public:
	vector<int> bits;
	Trie() {
		root = new Node();
		bits = vector<int>(31, 0);
	}


	void insert(int n) {

		Node *node = root;
		int x = n;
		for (int i = 0; i < 31; i++) {
			bits[i] = (x & 1);
			x >>= 1;
		}
		for (int i = 30; i >= 0; i--)
		{
			int bit = (bits[i]);
			if (!node->containsKey(bit))
				node->createTrie(bit, new Node());
			node = node->getKey(bit);
			node->inc(node);
		}
	}

	void remove(int n)
	{
		Node *node = root;
		int x = n;
		for (int i = 0; i < 31; i++) {
			bits[i] = (x & 1);
			x >>= 1;
		}
		for (int i = 30; i >= 0; i--) {
			int bit = (bits[i]);
			node = node->getKey(bit);
			node->dec(node);
		}
	}

	int getMax(int x)
	{
		Node *node = root;
		int _xor = 0;
		int _x = x;
		for (int i = 0; i < 31; i++) {
			bits[i] = (_x & 1);
			_x >>= 1;
		}
		for (int i = 30; i >= 0; i--)
		{
			int bit = (bits[i]);
			if (node->containsKey(1 - bit) && (node->getKey(1 - bit))->prefix)
			{
				_xor |= (1 << i);
				node = node->getKey(1 - bit);
			}
			else
				node = node->getKey(bit);
		}
		return _xor;
	}
};

void solve() {

	int n, x; cin >> n >> x;

	vector<int> a(n);
	for (auto &i : a) cin >> i;

	Trie trie;
	trie.insert(0);

	for (int i = 1; i < n; i++) a[i] ^= a[i - 1];

	auto f = [&](int m) -> int{
		int istd = -1;
		for (int i = 0; i < n; i++) {
			if (i - m >= 0) {
				trie.insert(a[i - m]);
				istd = i - m;
			}
			if (i >= m - 1 and trie.getMax(a[i]) >= x) {
				for (int j = 0; j <= istd; j++) trie.remove(a[j]);
				return i - m + 1;
			}
		}
		for (int j = 0; j <= istd; j++) trie.remove(a[j]);
		return -1;
	};

	int l = 1, r = n, ans = 1;
	while (l <= r) {

		int m = (l + r) / 2;
		int idx = f(m);

		if (idx != -1) {
			ans = m;
			l = m + 1;
		} else {
			r = m - 1;
		}
	}

	cout << f(ans) + 1 << " " << ans << "\n";

}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1; while (t--) solve();
	return 0;
}

• Subtask 1: 0 / 100