记录编号	299751	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015] Xor!	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	3.578 s
提交时间	2016-08-27 08:16:43	内存使用	0.62 MiB

#include <cstdio>
#include <queue>
typedef long long TYPE;
const int MAXN=50010;
struct lis{
	TYPE p,x,r;
	lis(int a=0,int b=0,int c=0){p=a;x=b;r=c;}
	bool operator <(const lis&a)
		const{return x<a.x;}
};
struct Node{
	Node*ch[2];
	int size;
	Node(){size=0;ch[0]=ch[1]=NULL;}
};
struct Tire{
	Node*root;
	Tire(){
		root=new Node();
	}
	void insert(TYPE x){
		bool t;Node*rt=root;
		for(int i=63;i>=0;--i){
			t=((x>>i)&1);
			//printf("t:%d i:%d\n",t,i);
			++(rt->size);
			if(rt->ch[t]==NULL)
				rt->ch[t]=new Node();
			rt=rt->ch[t];
		}++(rt->size);//printf("\n");
	}
	TYPE find(TYPE x,int rank){
		TYPE ans=0;
		bool t;Node*rt=root;
		for(int i=63;i>=0;--i){
			t=((x>>i)&1);
			if(rt->ch[!t]==NULL){
				rt=rt->ch[t];
				continue;
			}
			if(rt->ch[!t]->size<rank){
				rank-=(rt->ch[!t]->size);
				rt=rt->ch[t];
			}else {
				ans|=1<<i;
				rt=rt->ch[!t];
			}
		}return ans;
	}
}t;
std::priority_queue<lis>q;
TYPE w[MAXN];
int N,K;
int main(){
	freopen("_xor!.in","r",stdin);
	freopen("_xor!.out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;++i){
		scanf("%lld",&w[i]);
		t.insert(w[i]);
	}
	for(int i=1;i<=N;++i)
		q.push(lis(w[i],t.find(w[i],1),1));
	K*=2;
	for(int i=0;i<K;++i){
		lis p=q.top(); q.pop();
		if(!(i&1)) printf("%lld\n",p.x);
		q.push( lis(p.p , t.find(p.p , p.r+1),p.r+1) );
	}return 0;
}