Submission #21860

#	Time	Username	Problem	Language	Result	Execution time	Memory
21860		ulna	XOR (IZhO12_xor)	C++11	100 / 100	676 ms	99752 KiB

xor

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

// why am I so weak

int n, x;
int a[250055];

#define MAX_LOG 30

struct node {
	int res;
	node *left, *right;

	node(int res) : res(res) {left = NULL; right = NULL;}
} *root = new node(-1);

void insert(node *u, int x, int y, int w, int id) {
	if (x == y) {
		u->res = max(u->res, id);
		return;
	}

	int mid = (x + y) >> 1;

	if (!u->left) u->left = new node(-1);
	if (!u->right) u->right = new node(-1);

	if (w <= mid) insert(u->left, x, mid, w, id);
	else insert(u->right, mid + 1, y, w, id);

	u->res = max(u->res, max(u->left->res, u->right->res));
}
int query(node *u, int x, int y, int l, int r) {
	if (l > y || r < x) return -1;
	if (!u) return -1;

	if (l <= x && y <= r) return u->res;

	int mid = (x + y) >> 1;

	return max(query(u->left, x, mid, l, r), query(u->right, mid + 1, y, l, r));
}
int main() {
	scanf("%d %d", &n, &x);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		a[i] ^= a[i - 1];
	}

	int id = 0, k = -1;

	for (int i = n; i >= 1; i--) {
		insert(root, 0, (1 << 30) - 1, a[i], i);

		// a[j] ^ a[i - 1] >= x

		int cur = 0;

		for (int j = MAX_LOG - 1; j >= 0; j--) {
			if (x & (1 << j)) {
				// this bit is 1
				// must be 1

				if (!(a[i - 1] & (1 << j))) cur |= (1 << j); 
			} else {
				// this bit is 0
				// if 1 then greater

				int val = query(root, 0, (1 << 30) - 1, (a[i - 1] & (1 << j)) ? cur : cur | (1 << j), (a[i - 1] & (1 << j)) ? cur | ((1 << j) - 1) : (cur | ((1 << (j + 1)) - 1)));

				if (~val && val - i + 1 >= k) {
					id = i, k = val - i + 1;
				}

				if (a[i - 1] & (1 << j)) cur |= (1 << j);
			}
		}

		// check == x
		int val = query(root, 0, (1 << 30) - 1, cur, cur);

		if (~val && val - i + 1 >= k) {
			id = i, k = val - i + 1;
		}
	}

	printf("%d %d\n", id, k);

	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &x);
                        ^
xor.cpp:48:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^

• Subtask 1: 100 / 100