제출 #21859

#제출 시각아이디문제언어결과실행 시간메모리
21859ulnaXOR (IZhO12_xor)C++11
0 / 100
29 ms4712 KiB
#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 >= 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 >= k) { id = i, k = val - i + 1; } } printf("%d %d\n", id, k); return 0; }

컴파일 시 표준 에러 (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]);
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...