ZCMU--5162: 奖牌颁发

Description

小 D 希望在 2021 年的 ION 上拿到金牌，他无聊的时候在官网上看到了名额分配方案：

在所有获奖人员中有 20% 获得金牌，30% 获得银牌，剩下的 50% 获得铜牌。

特殊的，如果有很多人分数一样，那么他们获得相同的牌子。

但是这样会出现一个问题，大于某个分数的人的个数小于理论上拿金牌的人数，而加上这个分数的人数之后的总人数又大于理论上拿金牌的人数。这时，我们钦定这些人拿金牌。

并且拿金牌的人数如果比理论上的多，多出来的这部分占用银牌名额，如果银牌名额全部被占用，将没有选手获得银牌。

如果银牌名额占用了铜牌名额，处理方式同上。

例如一共有 10 个人有牌子拿，其中 8 个人分数相同且比剩下两个人分数高，那么这八个人拿金牌，剩下两个人拿铜牌。

现在小 D 告诉你所有有牌子的选手的分数，让你告诉他每个人分别是什么牌子。

Input

一行一个正整数 n 代表参赛选手的数量。

一行 n 个正整数代表每个参赛选手的分数。

对于 10% 的数据，每个选手不是 0 分就是 600 分。

对于 100% 的数据，1≤n≤2×106，选手分数都小于等于 600，选手人数一定是 10 的倍数。

Output

一行 n 个正整数代表每个选手的获奖情况，0 代表金牌，1 代表银牌，2 代表铜牌。

Sample Input

10

600  600  600  600  600  600  600  600  500  550

Sample Output

0  0  0  0  0  0  0  0  2  2

注意点：这题输出完最后不用换行😶，换行就PE了。

解析：我们利用结构体a[ ]存储每个选手的分数v，编号id和对应奖牌p，按照分数排序，假设初始金牌个数为J，那么前J个人肯定是金牌，然后从J+1个人开始，如果跟第J个人同分，那么他也是金牌，然后占用银牌数量，银牌不够了占用铜牌，如此遍历，但最后要按照输入顺序输出每个人的牌子，因此需要再开个b[ ]数组，遍历a[ ]，b[a[ i ].id ]=a[ i ].p，如此最后就按照输入顺序输出每个人的牌子。

#include 
#include 
using namespace std;
struct s
{
	int v,id,p;//记录每个人的分数v，编号id，对应牌子p
	bool operator<(const s&x)const{
		return v>x.v;//根据分数从大到小排序
	}
}a[2000005];
int b[2000005];//用来最后a[]按照id将对应牌子存到b[]中，因为要按照输入顺序输出
int main()
{
	int n,i,j,y,t,r;
	while(~scanf("%d",&n)){
		for(i=0;iscanf("%d",&a[i].v),a[i].id=i,a[i].p=2;//全部先初始化为铜牌🥉
		sort(a,a+n);//按照分数排序
		j=n*0.2,y=n*0.3,t=n*0.5;//分别算出理想各个牌子数量
		for(i=0;i0;//前j个人肯定是金牌
		for(i=j;i
			if(a[i].v!=a[i-1].v){
				r=i;
				break;
			}
			a[i].p=0;//表示跟金牌同分，也是金牌🥇
			if(y>0) y--;//占用银牌个数🥈
			else t--;//如果银牌用完了，占用铜牌🥉
		}
		//如果银牌还有剩余，跟上面同理
		if(y>0){
			for(i=r;i1;//r~r+y-1个人肯定是银牌
			for(i;i
				if(a[i].v!=a[i-1].v) break;
				a[i].p=1;
				t--;
			}	
		}
		for(i=0;i//将结果导入b[]，按照输入顺序记录每个人的牌子
		for(i=0;i
			if(i!=0) printf(" ");
			printf("%d",b[i]);
		}
	}
		return 0;
}