結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
big1.txt AC 241 ms
8,488 KB
big2.txt AC 197 ms
8,520 KB
big3.txt AC 140 ms
8,300 KB
big4.txt AC 205 ms
8,212 KB
big5.txt AC 207 ms
8,208 KB
big6.txt AC 171 ms
8,328 KB
big7.txt AC 260 ms
8,552 KB
big8.txt AC 150 ms
8,512 KB
big9.txt AC 146 ms
8,364 KB
big10.txt AC 177 ms
8,192 KB
gen_case1.txt AC 191 ms
8,172 KB
gen_case2.txt AC 221 ms
8,168 KB
gen_case3.txt AC 207 ms
8,168 KB
gen_case4.txt AC 144 ms
8,172 KB
gen_case5.txt AC 177 ms
8,168 KB
gen_case6.txt AC 124 ms
8,168 KB
gen_case7.txt AC 244 ms
8,168 KB
gen_case8.txt AC 237 ms
8,172 KB
gen_case9.txt AC 240 ms
8,168 KB
gen_case10.txt AC 142 ms
8,168 KB
gen_case11.txt AC 159 ms
8,172 KB
gen_case12.txt AC 152 ms
8,168 KB
gen_case13.txt AC 214 ms
8,168 KB
gen_case14.txt AC 178 ms
8,172 KB
gen_case15.txt AC 141 ms
8,168 KB
gen_case16.txt AC 199 ms
8,168 KB
gen_case17.txt AC 161 ms
8,168 KB
gen_case18.txt AC 202 ms
8,172 KB
gen_case19.txt AC 137 ms
8,168 KB
gen_case20.txt AC 214 ms
8,172 KB
in1 AC 4 ms
1,520 KB
in2 AC 4 ms
1,520 KB
system_test1.txt AC 239 ms
8,168 KB
system_test2.txt AC 251 ms
8,168 KB
system_test3.txt AC 152 ms
8,224 KB
test1 AC 4 ms
1,520 KB
test2 AC 4 ms
1,524 KB
test3 AC 3 ms
1,536 KB
test4 AC 4 ms
1,532 KB
test5 AC 6 ms
1,592 KB
test6 AC 6 ms
1,596 KB
test7 AC 15 ms
2,192 KB
test8 AC 14 ms
2,188 KB
test9 AC 14 ms
2,192 KB
test10 AC 14 ms
2,192 KB
test11 AC 8 ms
1,592 KB
test12 AC 39 ms
2,188 KB
test13 AC 40 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