记录编号	487080	评测结果	AAAAAAAAAA
题目名称	异或	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	2.308 s
提交时间	2018-02-09 08:56:06	内存使用	41.69 MiB

#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;
}