首页 > 其他分享 >CodeForces - 659B Qualifying Contest (模拟)水

CodeForces - 659B Qualifying Contest (模拟)水

时间:2023-06-08 14:02:26浏览次数:51  
标签:Qualifying region team CodeForces two each 659B qualifying define

Time Limit: 1000MS

 

Memory Limit: 262144KB

 

64bit IO Format: %I64d & %I64u

CodeForces - 659B


Qualifying Contest



Submit Status




Description




Very soon Berland will hold a School Team Programming Olympiad. From each of the m Berland regions a team of two people is invited to participate in the olympiad. The qualifying contest to form teams was held and it was attended by n Berland students. There were at least two schoolboys participating from each of the m regions of Berland. The result of each of the participants of the qualifying competition is an integer score from 0 to 800

The team of each region is formed from two such members of the qualifying competition of the region, that none of them can be replaced by a schoolboy of the same region, not included in the team and who received a greater

Your task is, given the results of the qualifying competition, to identify the team from each region, or to announce that in this region its formation requires additional contests.






Input




The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 10 000, n ≥ 2m) — the number of participants of the qualifying contest and the number of regions in Berland.

Next n lines contain the description of the participants of the qualifying contest in the following format: Surname (a string of length from 1 to 10 characters and consisting of large and small English letters), region number (integer from 1 to m) and the number of points scored by the participant (integer from 0 to 800, inclusive).

It is guaranteed that all surnames of all the participants are distinct and at least two people participated from each of the mregions. The surnames that only differ in letter cases, should be considered distinct.






Output




Print m lines. On the i-th line print the team of the i-th region — the surnames of the two team members in an arbitrary order, or a single character "?" (without the quotes) if you need to spend further qualifying contests in the region.






Sample Input





Input



5 2Ivanov 1 763Andreev 2 800Petrov 1 595Sidorov 1 790Semenov 2 503





Output



Sidorov IvanovAndreev Semenov





Input



5 2Ivanov 1 800Andreev 2 763Petrov 1 800Sidorov 1 800Semenov 2 503





Output



?Andreev Semenov



//题意:输入n,m,n表示有n个人,m表示这n个人来自m个不同的地区,接下来n行为n个人的个人信息,分别为名字,地区号,他的积分(积分越高,水平越高)。



现在每个地区要选出一个队伍去参见比赛,每个队伍有两个人组成,问这m个地区是否有确定的人选,有的话输出两个人的名字,如没有输出?。



Hait:样例二中地区1有三个大神,水平都是满级,但是不能确定让哪两个去,所以也是不确定的。




#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
#define IN __int64
#define N 100010 
#define M 1000000007
using namespace std;
struct zz
{
	char name[15];
	int area;
	int score;
}p[N];
bool cmp(zz a,zz b)
{
	if(a.area==b.area)
		return a.score>b.score;
	return a.area<b.area;
}
struct ss
{
	char name1[15];
	char name2[15];
	int k;
}s[N];
int main()
{
	int t,n,m,i,j,k;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%s%d%d",p[i].name,&p[i].area,&p[i].score);
		sort(p,p+n,cmp);
		int flag=0;
		i=1;j=0;
		while(i<=m&&j<n)
		{
			if(p[j].area!=i)
			{
				j++;
				continue;
			}
			if(p[j].area==i)
			{
				if(p[j+1].area==i)
				{
					if(p[j+2].area==i)
					{
						if(p[j+2].score==p[j+1].score)
							flag=1;
					}
				}
				else
					flag=1;
			}
			if(flag)
				s[i].k=1;
			else
			{
				strcpy(s[i].name1,p[j].name);
				strcpy(s[i].name2,p[j+1].name);
			}
			i++;flag=0;
		}
		for(i=1;i<=m;i++)
		{
			if(s[i].k)
				printf("?\n");
			else
				printf("%s %s\n",s[i].name1,s[i].name2);
		}
	}
	return 0;
}







标签:Qualifying,region,team,CodeForces,two,each,659B,qualifying,define
From: https://blog.51cto.com/u_16079508/6439522

相关文章

  • CodeForces - 670A Holidays (模拟) 水
    TimeLimit: 1000MS MemoryLimit: 262144KB 64bitIOFormat: %I64d&%I64uCodeForces-670AHolidaysSubmit StatusDescriptionOntheplanetMarsayearlastsexactly nInputThefirstlineoftheinputcontainsapositiveinteger n (1 ≤ n ≤ 1 000......
  • Codeforces Round 876 (Div. 2) 题解 A - D
    A.TheGoodArray题目大意给定两个整数\(n\)和\(k\),规定一个\(01\)数列为好的的条件是,对于\(1\simn\)中任意的\(i\),都有:\(a\)的前\(i\)个元素中至少有\(\lceil\frac{i}k\rceil\)个都是\(1\)。\(a\)的后\(i\)个元素中至少有\(\lceil\frac{i}k\rceil\)个都是......
  • codeforces.com/contest/1553/problem/B
    简单字符串哈希题意给一个字符串s和t,问从s的某个位置开始,向右到某个点后再向左,顺序遍历到的字符形成的字符串可否为t。思路数据只有500,\(O(n^3)\)可过,枚举转折点,然后枚举开头和结尾。代码intn,m,k;ullHash[1010],rHash[1010],p[1010],rp[1010],sum;voidsolve(){ ......
  • Codeforces Round 876 (Div. 2) A-D
    比赛地址A.TheGoodArray题意:定义一个数组是good的要求有:从左往右所有的i,前i个数中至少有[i/k]个数是1从右往左所有的i,前i个数中至少有[i/k]个数是1问good数组对于n而言最少需要多少个1Solution先从左往右填1,直到满足第一个条件,然后从右往左填1,直到满足第二个条件voidso......
  • ACM-CodeForces-#685(Div.2)
    A.SubtractorDivide#include<iostream>usingnamespacestd;intmain(){ intT,n; cin>>T; while(T--) { cin>>n; if(n<=3) n--; else n=2+(n&1); cout<<n<<endl; } return0;}B.Non-SubstringSubsequence#in......
  • Codeforces 1566G - Four Vertices(线段树分治)
    交了整整2页,本来想用随机化卡过去的,后来发现我的实现跑得太慢就写正常做法了。首先发现最优答案对应的四个点只可能有以下两种可能:\(a,b\)间有边,\(c,d\)间有边,此时答案是\(a,b\)边权值加\(c,d\)边权值。\(a\)与\(b,c,d\)三个点间都有边,此时答案是三条边权值之和。......
  • Codeforces 1801D The way home
    看到shortestpaths来做的。首先有一个贪心的策略,对于当前点\(u\)若不能直接往后走则肯定是选择经过的点中\(w_i\)最大的加。很好理解,证明就不需要了。所以可以定义状态\(f_{u,mx}\)为\(u\)点最大能加的值为\(h_{mx}\)的最优状态,\(h\)是\(w\)离散化后的数组。......
  • Codeforces 1588F - Jumping Through the Array
    显然无法用polylog的数据结构维护,序列分块也不行,考虑询问分块。每\(B\)个询问处理一次。将这个询问中\(2,3\)操作涉及到的点设为“关键点”,那么容易发现,环上每一段以关键点结尾的链在这块操作的过程中始终保持不变,也就是说我们可以把它们缩在一起。先预处理出每个块的增量......
  • Codeforces 1495F - Squares
    不知道怎么放到div1F的,感觉没啥亮点。首先对于一条\(1\)到\(n+1\)的路径而言,它经过的点的编号一定是递增的,也就是说,如果我们将关键点大小排个序,那么答案就是相邻两点间最短路的和。删/加点造成的变化是\(O(1)\)的,所以问题等价于,多次询问这张图中\(x,y\)之间最短路的......
  • Codeforces Round 876 (Div. 2)
    PrefaceDP腐乳闪总出列!(本来以为大掉分的一把,但这个号因为挺新的所以竟然还能上挺多分的,压线完成了5场上紫)早知道去做E题了,感觉CF真得要看题目相性,有些题目就是一眼感觉不适合自己的说A.TheGoodArray一个要动点脑子的签到题,因为\(a_1,a_n\)必须等于\(1\),然后中间的\(n-1\)......