Submission #612003

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612003	2022-07-29T09:52:50 Z	tranxuanbach	Hiring (IOI09_hiring)	C++17	100 / 100	621 ms	22200 KB

hiring

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 5e5 + 5;

struct candidate_t{
    int s, q, idx;

    candidate_t(){

    }

    candidate_t(int s, int q, int idx): s(s), q(q), idx(idx){

    }

    friend bool operator< (const candidate_t &lhs, const candidate_t &rhs){
        return lhs.s * rhs.q < rhs.s * lhs.q;
    }
};

int n; ll m;
candidate_t a[N];

multiset <pii> mtsq; ll sumq;

pair <int, ld> ans;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m;
    ForE(i, 1, n){
        cin >> a[i].s >> a[i].q; a[i].idx = i;
    }

    sort(a + 1, a + n + 1);
    ForE(i, 1, n){
        mtsq.emplace(a[i].q, a[i].idx); sumq += a[i].q;
        while (m * a[i].q < a[i].s * sumq){
            sumq -= prev(mtsq.end())->fi;
            mtsq.erase(prev(mtsq.end()));
        }
        ans = max(ans, make_pair(isz(mtsq), -(ld)a[i].s * sumq / a[i].q));
    }
    if (ans.fi == 0){
        cout << ans.fi << endl;
        return 0;
    }
    cout << ans.fi << endl;
    mtsq.clear(); sumq = 0;
    ForE(i, 1, n){
        mtsq.emplace(a[i].q, a[i].idx); sumq += a[i].q;
        while (m * a[i].q < a[i].s * sumq){
            sumq -= prev(mtsq.end())->fi;
            mtsq.erase(prev(mtsq.end()));
        }
        if (ans.fi == isz(mtsq) and abs(ans.se + (ld)a[i].s * sumq / a[i].q) <= 1e-6){
            Fora(elem, mtsq){
                cout << elem.se << endl;
            }
            return 0;
        }
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	328 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	3 ms	396 KB	Output is correct
12	Correct	5 ms	736 KB	Output is correct
13	Correct	4 ms	468 KB	Output is correct
14	Correct	8 ms	852 KB	Output is correct
15	Correct	9 ms	980 KB	Output is correct

Subtask #2
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	328 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	11 ms	1088 KB	Output is correct
5	Correct	24 ms	2216 KB	Output is correct
6	Correct	240 ms	12292 KB	Output is correct
7	Correct	331 ms	16956 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct

Subtask #4
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct

Subtask #5
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct

Subtask #6
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	4908 KB	Output is correct
2	Correct	85 ms	4876 KB	Output is correct
3	Correct	83 ms	4860 KB	Output is correct

Subtask #7
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	110 ms	8360 KB	Output is correct
2	Correct	155 ms	8396 KB	Output is correct
3	Correct	109 ms	8400 KB	Output is correct

Subtask #8
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	18992 KB	Output is correct
2	Correct	355 ms	18936 KB	Output is correct
3	Correct	341 ms	19032 KB	Output is correct

Subtask #9
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	594 ms	22200 KB	Output is correct
2	Correct	614 ms	22184 KB	Output is correct
3	Correct	621 ms	22152 KB	Output is correct

Submission #612003

Compilation message