답안 #21860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
21860	2017-04-26T13:51:07 Z	ulna	XOR (IZhO12_xor)	C++11	100 / 100	676 ms	99752 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3128 KB	Output is correct
2	Correct	0 ms	3128 KB	Output is correct
3	Correct	0 ms	3128 KB	Output is correct
4	Correct	3 ms	3392 KB	Output is correct
5	Correct	36 ms	4712 KB	Output is correct
6	Correct	33 ms	4844 KB	Output is correct
7	Correct	26 ms	4844 KB	Output is correct
8	Correct	46 ms	4976 KB	Output is correct
9	Correct	256 ms	49592 KB	Output is correct
10	Correct	236 ms	49856 KB	Output is correct
11	Correct	226 ms	49592 KB	Output is correct
12	Correct	216 ms	49724 KB	Output is correct
13	Correct	219 ms	49724 KB	Output is correct
14	Correct	239 ms	49856 KB	Output is correct
15	Correct	249 ms	49724 KB	Output is correct
16	Correct	223 ms	49724 KB	Output is correct
17	Correct	649 ms	99620 KB	Output is correct
18	Correct	599 ms	99752 KB	Output is correct
19	Correct	676 ms	99752 KB	Output is correct
20	Correct	516 ms	99620 KB	Output is correct