Submission #405611

#	Time	Username	Problem	Language	Result	Execution time	Memory
405611		Aldas25	Hiring (IOI09_hiring)	C++14	84 / 100	1591 ms	19988 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;
pair<ll, ll> mn;
priority_queue<pair<ll, int>> qu;

pair<ll, int> tp;
pair<ll, ll> curCost;

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

    while (!qu.empty()) {qu.pop();}

    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};

        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;
}

pair<ll, ll> check2 (int k, bool print=false) {
    //cout << " checking k = " << k << endl;
    while (!qu.empty()) {qu.pop();}

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

        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;
           // }
            if (curSum * curCost.f * ret.s <= ret.f * curCost.s) {
                ret = {curSum*curCost.f, curCost.s};
            }

            if (print && ret.f * mn.s == ret.s * mn.f) {
                while (!qu.empty()) {
                    cout << qu.top().s << "\n";
                    qu.pop();
                }
                return ret;
            }
        }
    }

    return ret;
}

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) {
        mn = check2(le);
        check2 (le, true);
    }

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 24 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6