스터디 23/01/07 2535 : 아시아 정보올림피아드

2535번: 아시아 정보올림피아드 (acmicpc.net)

2535번: 아시아 정보올림피아드

풀이
점수를 기준으로 정렬 후 1등부터 3등을 선정한다.
이때 한 팀당 3명 이상이 메달을 얻을 수 없으므로 팀마다 메달을 획득한 인원수를 기록해준다.
3명을 모두 선정하면 종료한다.

 

시간복잡도 : O(nlogn), n <= 100

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


int main() {
    init();
    vector<pair<int, pii>> v;
    map<int,int> t;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int team, num, score;
        cin >> team >> num >> score;
        v.push_back({ score,{team,num} });
    }
    sort(v.begin(), v.end(),greater<pair<int,pii>>());

    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        if (cnt == 3)
            break;
        int team = v[i].second.first;
        int num = v[i].second.second;
        if (t[team] == 2) {
            continue;
        }
        cnt++;
        t[team]++;
        cout << team << " " << num << "\n";
    }
}