比赛 |
NOIP模拟赛1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
异或 |
最终得分 |
100 |
用户昵称 |
Chenyao2333 |
运行时间 |
2.317 s |
代码语言 |
C++ |
内存使用 |
31.07 MiB |
提交时间 |
2018-02-08 21:20:50 |
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int kN = 1e5 + 10;
int N, K;
int root[kN];
int t[kN*33][2], tcnt;
int val[kN*33];
int a[kN];
bool get(int v, int i) {
return (v & (1 << i) ) > 0;
}
void insert(int &x, int fa, int v, int deep) {
//printf("%d %d %d %d\n", x, fa, v, deep);
x = ++tcnt;
t[x][0] = t[fa][0];
t[x][1] = t[fa][1];
val[x] = val[fa] + 1;
if (deep == -1) {
return;
}
bool s = get(v, deep);
insert(t[x][s], t[fa][s], v, deep-1);
}
struct Ans{
int XOR;
int rv;
int left;
int k;
bool operator < (const Ans &ans) const {
return XOR > ans.XOR;
}
};
Ans find(int v, int x, int k) {
//printf("%d %d %d\n", v, x, k);
int left = x;
int K = k;
int XOR = 0;
for (int i = 29; i >= 0; i--) {
bool s = get(v, i);
//printf("val[t[x][s]] = %d\n", val[t[x][s]]);
if (val[t[x][s]] >= k) {
x = t[x][s];
} else {
k -= val[t[x][s]];
x = t[x][!s];
XOR ^= 1 << i;
}
if (i == 0) {
// printf("XOR: %d v: %d left: %d k: %d val[x]: %d\n", XOR, v, left, k, val[x]);
if (val[x] >= k) {
return (Ans){XOR, v, left, K};
} else {
return (Ans){-1, -1, -1, -1};
}
}
}
}
int main() {
freopen("xorxor.in", "r", stdin);
freopen("xorxor.out", "w", stdout);
scanf("%d %d", &N, &K);
for (int i = 1; i <= N; i++) {
int v;
scanf("%d", &v);
insert(root[i], root[i-1], v, 29);
//printf("root[%d]= %d\n", i, root[i]);
//fflush()
a[i] = v;
}
//printf("hi\n");
priority_queue<Ans> q;
for (int i = 2; i <= N; i++) {
Ans ans = find(a[i], root[i-1], 1);
q.push(ans);
}
while (q.size()) {
Ans ans = q.top();
q.pop();
K--;
if (K == 0) {
printf("%d\n", ans.XOR);
return 0;
}
ans = find(ans.rv, ans.left, ans.k+1);
if (ans.XOR == -1) {
continue;
}
q.push(ans);
}
return 0;
}