Codeforces 659B - Qualifying Contest

문제

http://codeforces.com/contest/659/problem/B

대략 해석해보자면 전국 프로그래밍 대회가 열리는데 그 전에 지역마다 예선을 치뤄서 각 지역마다 대표 2명을 뽑아서 참가하게 하려는데 대표 2명을 구성할수 있는 경우가 유니크(단 한 가지)한지 판별해야 하는 문제이다.

입력은 첫 줄에 전체 학생 수 N과 전체 지역 수 M이 들어오고 2번째 줄부터 N+1번째 줄까지 이름, 지역 번호, 점수(0~800)가 들어온다.

우리는 그 데이터를 가지고 각 지역의 대표를 구성할수 있는 경우가 유니크한지, 유니크 하다면 점수->이름(Sort by score, then by name)순으로 정렬된 대표들을 출력하는 것이다. 만약에 유니크하지 않는다면 ?를 출력하면 된다.

풀이

배열에 이름과 점수를 모두 가지고 정렬을 해야하므로 map을 사용할까 set을 사용할까 생각하다가 그냥 vector<pair<string,int>>를 사용하기로 결정하고 해당 vector를 배열로 만들어 vector[지역번호] 식으로 사용하였다.

학생의 이름, 지역 번호, 점수를 받은 뒤 vector[지역 번호].push_back(make_pair(이름, 점수)) 식으로 데이터를 넣었고 정렬은 <algorithm>에 있는 stable_sort를 이용하여 직접 점수 정렬 후 이름 정렬을 구현 하였다.

또한 각 팀마다 같은 점수가 몇 명 있는지 확인하기 위해 hi라는 배열을 만들어 기저 사례를 처리하였다.

기저 사례

1. 가장 높은 점수가 2명이면 바로 해당 학생들의 이름을 출력

2. 가장 높은 점수가 3명 이상 있거나 한 지역의 참가 학생이 2명보다 적으면 ?를 출력

또한 가장 높은 점수가 1명이더라도 두번째로 높은 점수가 여러명이면 유니크한 경우가 아니므로 확인 후 ?를 출력하게 하였다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define INT_MAX 987654321
using namespace std;

bool cmp(const pair<string,int>& val1, const pair<string,int>& val2){
	if(val1.second!=val2.second)
		return val1.second>val2.second;
	else
		return val1.first<val2.first;
}

int main()
{
	int n,m,i,j,**hi;
	vector<pair<string,int>> *v;

	cin.sync_with_stdio(false);
	cin>>n>>m;
	v = new vector<pair<string,int>>[m+1];
	hi = new int*[m+1];

	for(i=1;i<=m;i++){
		hi[i] = new int[801]();
	}

	for(i=0;i<n;i++){
		string name;
		int team,score;

		cin>>name>>team>>score;

		v[team].push_back(make_pair(name,score));
		hi[team][score]++;
	}

	for(i=1;i<=m;i++){
		stable_sort(v[i].begin(),v[i].end(),cmp);

		if(hi[i][v[i][0].second]>2 || v[i].size() < 2) {
			cout << "?\n";
		}
		else {      
			if(hi[i][v[i][0].second] == 2)
			{
				cout << v[i][0].first << " " << v[i][1].first << "\n";
				continue;
			}

			int secondary = INT_MAX;

			for(j=0;j<v[i].size();j++){
				if(v[i][0].second != v[i][j].second){
					secondary = v[i][j].second;
					break;
				}
			}

			if(secondary != INT_MAX && hi[i][secondary]>1)
				cout << "?\n";
			else
				cout << v[i][0].first << " " << v[i][1].first << "\n";
		}
	}
}