Submission #405596

#	Time	Username	Problem	Language	Result	Execution time	Memory
405596		Aldas25	Hiring (IOI09_hiring)	C++14	60 / 100	1250 ms	22132 KiB

hiring

#pragma GCC optimize("O2")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 500100, MAXK = 30;
const ll MOD = 998244353;
const int INF = 1e9;
const ld PI = asin(1) * 2;

bool cmp (pair<pair<ll, ll>, int> a, pair<pair<ll, ll>, int> b) {
    return a.f.f * b.f.s < a.f.s * b.f.f;
}

int n;
ll w;
vector<pair<pair<ll, ll>, int>> seq;

bool check (int k, bool print = false) {
    //cout << " checking k = " << k << endl;
    priority_queue<pair<ll, int>> qu;

    pair<ll, ll> curCost = {0, 1};
    ll curSum = 0;
    for (auto p : seq) {
        ll s = p.f.f, q = p.f.s;
        int id = p.s;
        curCost = {s, q};

        pair<ll, int> tp = {-1, -1};
        if ((int)qu.size() == k) {
            tp = qu.top();
            qu.pop();
            curSum -= tp.f;
        }
        if (tp.f == -1 || tp.f > q) tp = {q, id};
        qu.push(tp);
        curSum += tp.f;

        if ((int)qu.size() == k) {
            if (curSum * curCost.f <= w * curCost.s) {
                if (print) {
                    while (!qu.empty()) {
                        auto tpp = qu.top();
                        cout << tpp.s << "\n";
                        qu.pop();
                    }
                }
                return true;
            }
        }
    }

    return false;
}

int main()
{
    FAST_IO;

    cin >> n >> w;
    FOR(i, 1, n) {
        ll s, q; cin >> s >> q;
        seq.pb({{s, q}, i});
    }

    sort(seq.begin(), seq.end(), cmp);

    int le = 0, ri = n;
    while (le < ri) {
        int mid = (le+ri+1)/2;
        if (check(mid)) le = mid;
        else ri = mid-1;
    }

    cout << le << "\n";
    if (le > 0) check (le, true);

    return 0;
}

• Subtask 1: 19 / 30
• Subtask 2: 20 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 3 / 6
• Subtask 8: 3 / 6
• Subtask 9: 3 / 6