Submission #1101228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101228		muntasir__	XOR (IZhO12_xor)	C++17	0 / 100	13 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 = 30;
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;
	cnt[node] = min(idx, cnt[node]);
	for (int i = B; i >= 0; i--) {
		int k = val >> i & 1;
		if (trie[node][k] == -1) {
			trie[node][k] = ++num;
			cnt[num] = min(cnt[num], idx);
		}
		node = trie[node][k];
	}
}
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 ans = 0, 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];
			}
		}
	}
	if (cur >= k)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 x;
		cin >> x;
		cur ^= x;
		// cout << i << "\n";
		int val = query(cur, k);
		// cout << val << endl;
		if (val == 1) {
			int dis = (i - val + 1);
			if (dis > k) {
				k = dis;
				idx = val;
			}
		}
		insert(cur, i + 1);
	}
	// for (int i = 0; i < num; i++)cout << i << ": " << cnt[i] << "\n";
	cout << idx + 1 << " " << k << "\n";
}

Compilation message (stderr)

xor.cpp: In function 'int query(int, int)':
xor.cpp:45:6: warning: unused variable 'ans' [-Wunused-variable]
   45 |  int ans = 0, cur = 0, node = 0;
      |      ^~~

• Subtask 1: 0 / 100