记录编号	34038	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]瑞士轮	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	1.630 s
提交时间	2011-11-26 22:31:13	内存使用	10.14 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("swiss.in");
ofstream fout("swiss.out");

int N,R,Q;

class Competitor
{
public:
	int Score,Name,Energy;
}Single[200001],A1[200001],A2[200001];
int L1,L2;
int Compare(const void *p,const void *q)
{
Competitor *p1=(Competitor *)p;
Competitor *p2=(Competitor *)q;
	if(p1->Score == p2->Score)
	{
		if(p1->Name > p2->Name)
			return 1;
		else
			return -1;
	}
	else
		return p2->Score - p1->Score;
}

int main()
{
int i,j,k;
	fin>>N>>R>>Q;
	N*=2;
	for(i=1;i<=N;i++)
	{
		fin>>Single[i].Score;
		Single[i].Name=i;
	}
	for(i=1;i<=N;i++)
		fin>>Single[i].Energy;
		qsort(Single+1,N,sizeof(Competitor),Compare);
int p1,p2,L,p;
	for(i=1;i<=R;i++)
	{
		L1=0;L2=0;
		int Ti=N/2;
		for(j=1;j<=N;j++)
		{
			A1[j].Score=0;
			A2[j].Score=0;
		}
		for(j=1;j<=Ti;j++)
		{
			k=j<<1;
			if(Single[k].Energy > Single[k-1].Energy)
			{
				Single[k].Score++;
				A1[++L1]=Single[k];
				A2[++L2]=Single[k-1];
			}
			else
			{
				Single[k-1].Score++;
				A1[++L1]=Single[k-1];
				A2[++L2]=Single[k];
			}
		}
		p1=1;p2=1;L=L1;
		int q=0;
		
		for(j=1;j<N;j++)
		{
			if(A1[p1].Score > A2[p2].Score)
				Single[++q]=A1[p1++];
			else
			{
				if(A1[p1].Score < A2[p2].Score)
					Single[++q]=A2[p2++];
				else
				{
					if(A1[p1].Name > A2[p2].Name)
						Single[++q]=A2[p2++];
					else
						Single[++q]=A1[p1++];
				}
			}
			
			if(p1 > L1)
			{
				int d=p2;
				for(j=L1+1;j<=N;j++)
					Single[++q]=A2[d++];
				break;
			}
			if(p2 > L2)
			{
				int d=p1;
				for(j=L2+1;j<=N;j++)
					Single[++q]=A1[d++];
				break;
			}
		}
	}
	
	qsort(Single+1,N,sizeof(Competitor),Compare);
	
	fout<<Single[Q].Name;
	
	fin.close();
	fout.close();
	return 0;
}