记录编号	75871	评测结果	AAAAAAAAAA
题目名称	625.[NOIP 2011]瑞士轮	最终得分	100
用户昵称	wakawaka	是否通过	通过
代码语言	C++	运行时间	0.928 s
提交时间	2013-10-29 14:04:26	内存使用	4.89 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,r,q,i,j,ji;
struct node
{
	int s,p,ii;
}a[200010],w[100010],l[100010];

bool cmp(node a,node b)
{
	if (a.s==b.s) return a.ii<b.ii;
	return a.s>b.s;
}
int main()
{  
	freopen("swiss.in","r",stdin);
	freopen("swiss.out","w",stdout);
	cin>>n>>r>>q; n*=2;
	for ( i=1;i<=n;++i) scanf("%d",&a[i].s),a[i].ii=i;
	for ( j=1;j<=n;++j) scanf("%d",&a[j].p);
	sort(a+1,a+1+n,cmp);
	for ( ji=1;ji<=r;ji++)
	 {  
	    int wi=1,lo=1;
	 	for ( i=1;i<=n;i+=2)
	 	{
	 		if (a[i].p<a[i+1].p) w[wi++]=a[i+1],l[lo++]=a[i]; 
	 		else if (a[i].p>a[i+1].p)l[lo++]=a[i+1],w[wi++]=a[i];
	 	}
	 	wi--;lo--;
	 	for ( i=1;i<=n/2;i++) w[i].s++;
	 	int x=1,y=1;
	 	i=0;
		while( x<=n/2 && y<=n/2)
	 	{
	 		if (w[x].s>l[y].s) a[++i]=w[x++];
	 	    if (w[x].s<l[y].s) a[++i]=l[y++];
			if (w[x].s==l[y].s&&w[x].ii>l[y].ii) a[++i]=l[y++];
	 		if (w[x].s==l[y].s&&w[x].ii<l[y].ii) a[++i]=w[x++];
		 }
		 if (x>n/2) 
		while (y<=n/2) 
		a[++i]=l[y++];      
		else while (x<=n/2) 
		a[++i]=w[x++];
	 }
	 printf("%d",a[q].ii);
}