Submission #970966

#	Time	Username	Problem	Language	Result	Execution time	Memory
970966		Bilyana	Hiring (IOI09_hiring)	C++17	88 / 100	270 ms	17500 KiB

hiring

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <list>
#include <set>
#include <vector>
#include <string>
#include <math.h>
#include <queue>
 
#define f first
#define s second
#define sz(a) ((long long)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
 
using namespace std;
using ll = long long;
 
template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is,       pair<T, T2> &p)             { is>>p.f>>p.s;        return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p)             { os<<p.f<<' '<<p.s;   return os; }
template<class T>           inline istream &operator>>(istream &is,       vector<T> &v)               { for (auto &id : v)   is>>id;       return is; }
template<class T>           inline ostream &operator<<(ostream &os, const vector<T> &v)               { for (auto id : v)    os<<id<<'\n';  return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m)              { for (auto id : m)    os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um)   { for (auto id : um)   os<<id<<'\n'; return os; }
template<class T>           inline ostream &operator<<(ostream &os, const list<T> &l)                 { for (auto id : l)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const set<T> &s)                  { for (auto id : s)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const unordered_set<T> &us)       { for (auto id : us)   os<<id<<' ';  return os; }
const long long INF = 1e18;
const bool hasTests = 1;
 
long long n;
long long w;
vector<pair<long long, long long>> k;
vector<long long> ansWork;
 
void input() {
    cin >> n >> w;
    k.resize(n);
    cin >> k;
}
 
void output() {
    cout << ansWork.size() << endl;
    cout << ansWork;
}
 
void solve() {
    vector<int> perm (n);
    for (int i=0; i<n; i++) {
        perm[i] = i;
    }
    sort(perm.begin(), perm.end(), [&](auto l, auto r) {
        if ((float)k[l].f / k[l].s == (float)k[r].f / k[r].s) {
            return k[l].s < k[r].s;
        }
        return (float)k[l].f / k[l].s < (float)k[r].f / k[r].s;
    });
 
    long long ans = 0;
    long long bestWork = 0;
    float bestMoney = 0;
 
    long long sz = 0;
    long long qu = 0;
    float money = 0;
    float tot = 0;
    priority_queue<long long> curr;
 
    long long i = 0;
    for (auto temp : perm) {
        auto work = k[temp];
        qu += work.s;
        money = (float)work.f / work.s;
        sz++;
        curr.push(work.s);
 
        tot = (float)qu * money;
        while (!curr.empty() && tot > (float)w) {
            qu -= curr.top();
            curr.pop();
            tot = (float)qu * money;
            sz--;
        }
 
        if ((sz > bestWork) || (sz == bestWork && tot < bestMoney)) {
            bestWork = sz;
            bestMoney = tot;
            ans = i; 
        }
        i++;
    }
 
    qu = 0;
    for (long long i=0; i<=ans; i++) {
        ansWork.push_back(perm[i]);
        qu += k[perm[i]].second;
    }
    money = (float)k[perm[ans]].first / k[perm[ans]].second;
 
    sort(ansWork.begin(), ansWork.end(), [&](auto l, auto r) {
        return k[l].s < k[r].s;
    });
 
    tot = (float)money * qu;
 
    while (tot > (float)w && !ansWork.empty()) {
        qu -= k[ansWork.back()].s;
        tot = (float)money * qu;
        ansWork.pop_back();
    }
 
    for (auto& curr : ansWork) {
        curr++;
    }
}
 
void start() {
    input();
    solve();
    //cout<<"Case #"<<i<<": ";
    output();
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    start();
    return 0;
}

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