Submission #1101241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101241		muntasir__	XOR (IZhO12_xor)	C++17	0 / 100	15 ms	91216 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 = 2;
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 val, int idx) {
	int node = 0;
	for (int i = B; i >= 0; i--) {
		int k = val >> i & 1;
		if (trie[node][k] == -1) {
			trie[node][k] = ++num;
			cnt[num] = idx;
		}
		node = trie[node][k];
		cnt[node] = min(cnt[node], idx);
	}
}
void del(int val) {
	int node = 0;
	cnt[node]--;
	for (int i = B; i >= 0; i--) {
		int k = val >> i & 1;
		if (trie[node][k] == -1) {
			break;
		}
		int prev = node;
		node = trie[node][k];
		cnt[node]--;
		if (cnt[node] == 0) {
			trie[prev][k] = -1;
		}
	}
}
//number of subarray such that xor(a[i])>=k
int query(int val, int k) {
	int temp = k, cur = 0, node = 0;
	for (int i = B; i >= 0; i--) {
		if (node == -1)return -1;
		int b1 = val >> i & 1, b2 = k >> i & 1;
		// cout << node << " " << cnt[node] << endl;
		if (b2 == 1) {
			if (trie[node][!b1] != -1) {
				node = trie[node][!b1];
				cur |= (1 << i);
			} else {
				node = trie[node][b1];
			}
		} else {
			if (trie[node][!b1] != -1) {
				node = trie[node][!b1];
				cur |= (1 << i);
			} else {
				node = trie[node][b1];
			}
		}
	}
	// cout << cur << " " << temp << " " << node << " " << cnt[node] << endl;
	if (cur >= temp)return cnt[node];
	else return -1;
}
int get_max(int val) {
	int node = 0, ans = 0;
	for (int i = B; i >= 0; i--) {
		int k = val >> i & 1;
		if (trie[node][!k] != -1) {
			ans <<= 1; ans++;
			node = trie[node][!k];
		} else {
			ans <<= 1;
			node = trie[node][k];
		}
	}
	return ans;
}
int get_min(int val) {
	int node = 0, ans = 0;
	for (int i = B; i >= 0; i--) {
		int k = val >> i & 1;
		if (trie[node][k] != -1) {
			ans <<= 1;
			node = trie[node][k];
		} else {
			ans <<= 1; ans++;
			node = trie[node][!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(cur, INT32_MAX);
	int idx = n, k = 0;
	for (int i = 0; i < n; i++) {
		int y;
		cin >> y;
		cur ^= y;
		// cout << i << " ";
		int val = query(cur, x);
		// cout << i << " " << val << endl;
		if (val != -1) {
			// cout << i << endl;
			if (val == INT32_MAX)val = -1;
			int dis = (i - val);
			// cout << dis << " " << k << endl;
			if (dis > k) {
				k = dis;
				idx = val + 1;
				// cout << i << " " << k << " " << val << " " << idx << endl;
			}
		}
		insert(cur, i);
	}
	// for (int i = 0; i <= num; i++)cout << i << ": " << cnt[i] << "\n";
	cout << idx + 1 << " " << k << "\n";
}

• Subtask 1: 0 / 100