[백준] 3758 KCPC

문제

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.) 

당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다. 

점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다. 

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 

동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라. 

서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다. 

 

 

정렬 문제입니다.

 

구조체를 작성해주고, 주어진 조건에 맞춰 정렬하는게 핵심입니다.

 

struct TEAM {
	int id = 0;
	int latest = 0;
	int query[101] = { 0 };
	int cnt = 0;
	int score = 0;
};

 

그리고 정렬하는 sort의 비교함수 compare은 다음과 같습니다.

bool compare(TEAM& a, TEAM& b) {
	if (a.score > b.score)return true;
	else if (a.score < b.score)return false;

	if (a.cnt < b.cnt)return true;
	else if (a.cnt > b.cnt)return false;

	if (a.latest < b.latest)return true;
	return false;
}

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
int TC, N, K, T, M, I, J, S;
struct LOG {
	int num;
	int id;
	int s;
	int t;
};
struct TEAM {
	int id = 0;
	int latest = 0;
	int query[101] = { 0 };
	int cnt = 0;
	int score = 0;
};
bool compare(TEAM& a, TEAM& b) {
	if (a.score > b.score)return true;
	else if (a.score < b.score)return false;

	if (a.cnt < b.cnt)return true;
	else if (a.cnt > b.cnt)return false;

	if (a.latest < b.latest)return true;
	return false;
}

int main() {
	FAST;
	cin >> TC;
	while (TC--) {
		TEAM teams[101];
		cin >> N >> K >> T >> M;
		//팀 의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m
		int ti = 0;
		REP(i, N)teams[i].id = i;
		while (M--) {
			cin >> I >> J >> S;
			// 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 
			//LOG log = { J,I,S,++ti };
			teams[I].latest = ++ti;
			teams[I].cnt++;
			teams[I].query[J] = max(teams[I].query[J], S);
		}
		REP(i, N) {
			REP(j, K) {
				teams[i].score += teams[i].query[j];
			}
		}
		sort(teams + 1, teams + 1+ N, compare);
		REP(i, N) {
			if (teams[i].id == T) {
				cout << i << "\n";
				break;
			}
		}
	}
}