문제
프로그래밍 대회의 제출 로그가 주어질 때, 맞은 문제 수 내림차순, 같으면 총 페널티 시간 오름차순으로 순위를 매겨라.
입력
테스트 케이스 수 K, 각 케이스에 문제 수 M, 제출 수 N, 참가자 수 P, 이후 N개의 제출 로그(참가자번호, 문제, 시각, 정답여부)가 주어진다.
출력
각 케이스마다 참가자를 순위순으로 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3 5 2 ... | Data Set 1: ... |
풀이
각 참가자의 맞은 문제 수와 페널티를 집계한 뒤 정렬한다.
- 각 제출에 대해 이미 맞은 문제는 무시한다
- 정답이면 맞은 수를 증가시키고, 페널티 = 제출 시각 + 오답 횟수 * 20을 누적한다
- 오답이면 해당 문제의 오답 횟수를 증가시킨다
- 맞은 문제 수 내림차순, 페널티 오름차순으로 정렬하여 출력한다
핵심 아이디어: ICPC 스타일 스코어보드로, 맞은 문제가 많을수록 유리하고, 같으면 페널티가 적은 쪽이 상위이다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(vector<int> a, vector<int> b)
{
if (a[1] != b[1])
return a[1] > b[1];
return a[2] < b[2];
}
int main()
{
int K;
cin >> K;
int M, N, P;
int p, t, j;
char m;
for (int i = 1; i <= K; i++)
{
cin >> M >> N >> P;
vector<vector<int>> userList(P, vector<int>(3));
vector<vector<int>> wrongList(P, vector<int>(M));
for (int i = 0; i < P; i++)
userList[i][0] = i + 1;
for (int i = 0; i < N; i++)
{
cin >> p >> m >> t >> j;
if (wrongList[p - 1][m - 'A'] == -1)
continue;
if (j)
{
userList[p - 1][1]++;
userList[p - 1][2] += t + wrongList[p - 1][m - 'A'] * 20;
wrongList[p - 1][m - 'A'] = -1;
}
else
{
wrongList[p - 1][m - 'A']++;
}
}
sort(userList.begin(), userList.end(), cmp);
cout << "Data Set " << i << ":\n";
for (int i = 0; i < P; i++)
{
for (int j = 0; j < 3; j++)
cout << userList[i][j] << " ";
cout << "\n";
}
cout << "\n";
}
}복잡도
- 시간: O(N + P log P)
- 공간: O(P * M)