记录编号	157431	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]明明的随机数	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-04-08 21:23:12	内存使用	0.28 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct Node{
	Node* ch[2];
	int r,v,s;
	
	void Maintain(){
		s=ch[0]->s+ch[1]->s+1;	
	}
	int cmp(int x) const{
		if(x==v) return -1;
		else return x<v?0:1;
	}
};

Node *null,*root;

void rotate(Node* &o,int d){
	Node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->Maintain();
	k->Maintain();
	o=k;
}

void insert(Node* &o,int x)
{
	if(o==null){
		o=new Node();o->ch[0]=o->ch[1]=null;o->r=rand();o->v=x;
		o->Maintain();
	}
	else{
		int d=o->cmp(x);
		insert(o->ch[d],x);
		o->Maintain();
		if(o->ch[d]->r > o->r) rotate(o,d^1);
	}
}

bool find(Node* u,int x)
{
	if(u==null) return false;
	int d=u->cmp(x);
	if(d==-1 || find(u->ch[d],x)) return true;
	return false;
}

void print(Node* o)
{
	if(o==null) return;
	print(o->ch[0]);
	printf("%d ",o->v);
	print(o->ch[1]);
}

void init()
{
	null=new Node();
	null->r=null->v=0;
	root=null;
}

void work()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		if(!find(root,x)) insert(root,x);
	}
	printf("%d\n",root->s);
	print(root);
}

int main()
{
	freopen("random.in","r",stdin);
	freopen("random.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}