Submission #612003

#	Time	Username	Problem	Language	Result	Execution time	Memory
612003		tranxuanbach	Hiring (IOI09_hiring)	C++17	100 / 100	621 ms	22200 KiB

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 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6