結果

問題 No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
ユーザー mayoko_
提出日時 2016-07-13 20:42:48
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 160 ms
コード長 1,961 Byte
コンパイル時間 751 ms
使用メモリ 8,544 KB
最終ジャッジ日時 2019-06-14 16:02:50

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
big1.txt AC 141 ms
8,484 KB
big2.txt AC 124 ms
8,516 KB
big3.txt AC 103 ms
8,300 KB
big4.txt AC 130 ms
8,208 KB
big5.txt AC 135 ms
8,204 KB
big6.txt AC 129 ms
8,328 KB
big7.txt AC 160 ms
8,544 KB
big8.txt AC 106 ms
8,500 KB
big9.txt AC 104 ms
8,360 KB
big10.txt AC 121 ms
8,192 KB
gen_case1.txt AC 125 ms
8,164 KB
gen_case2.txt AC 135 ms
8,168 KB
gen_case3.txt AC 134 ms
8,164 KB
gen_case4.txt AC 106 ms
8,168 KB
gen_case5.txt AC 123 ms
8,168 KB
gen_case6.txt AC 96 ms
8,168 KB
gen_case7.txt AC 152 ms
8,164 KB
gen_case8.txt AC 146 ms
8,168 KB
gen_case9.txt AC 151 ms
8,168 KB
gen_case10.txt AC 102 ms
8,168 KB
gen_case11.txt AC 108 ms
8,168 KB
gen_case12.txt AC 110 ms
8,164 KB
gen_case13.txt AC 138 ms
8,164 KB
gen_case14.txt AC 119 ms
8,164 KB
gen_case15.txt AC 100 ms
8,168 KB
gen_case16.txt AC 130 ms
8,164 KB
gen_case17.txt AC 107 ms
8,164 KB
gen_case18.txt AC 127 ms
8,168 KB
gen_case19.txt AC 102 ms
8,168 KB
gen_case20.txt AC 137 ms
8,164 KB
in1 AC 3 ms
1,520 KB
in2 AC 3 ms
1,520 KB
system_test1.txt AC 144 ms
8,164 KB
system_test2.txt AC 151 ms
8,168 KB
system_test3.txt AC 106 ms
8,220 KB
test1 AC 3 ms
1,520 KB
test2 AC 2 ms
1,516 KB
test3 AC 3 ms
1,532 KB
test4 AC 3 ms
1,532 KB
test5 AC 4 ms
1,592 KB
test6 AC 4 ms
1,592 KB
test7 AC 11 ms
2,188 KB
test8 AC 11 ms
2,188 KB
test9 AC 11 ms
2,184 KB
test10 AC 12 ms
2,188 KB
test11 AC 5 ms
1,592 KB
test12 AC 23 ms
2,188 KB
test13 AC 23 ms
2,188 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

struct Team {
    int id;
    int solve;
    int penalty;
    int univ;
    int sameUpper;
    Team() {}
    Team(int id, int solve, int penalty, int univ) : id(id), solve(solve), penalty(penalty), univ(univ) {}
};

bool comp1(const Team& lhs, const Team& rhs) {
    if (lhs.solve != rhs.solve) return lhs.solve > rhs.solve;
    return lhs.penalty < rhs.penalty;
}

bool comp2(const Team& lhs, const Team& rhs) {
    if (lhs.solve != rhs.solve) return lhs.solve > rhs.solve;
    if (lhs.sameUpper != rhs.sameUpper) return lhs.sameUpper < rhs.sameUpper;
    return lhs.penalty < rhs.penalty;
}

const int MAXN = 100100;
Team teams[MAXN];
int memo[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    set<pii> S;
    assert(1 <= N && N <= 100000 && 1 <= K && K <= N);
    for (int i = 0; i < N; i++) {
        int s, p, u;
        cin >> s >> p >> u;
        assert(0 <= s && s <= 10);
        assert(0 <= p && p <= 1000000);
        assert(1 <= u && u <= 100000);
        teams[i] = Team(i, s, p, u);
        S.insert(pii(s, p));
    }
    assert(S.size() == N);
    sort(teams, teams+N, comp1);
    for (int i = 0; i < N; i++) {
        teams[i].sameUpper = memo[teams[i].univ]++;
    }
    sort(teams, teams+N, comp2);
    for (int i = 0; i < K; i++)
        cout << teams[i].id << endl;
    return 0;
}
0