Submission #335581

#	Time	Username	Problem	Language	Result	Execution time	Memory
335581		Joshc	Hiring (IOI09_hiring)	C++11	60 / 100	495 ms	29632 KiB

hiring

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define EPS 0.0000001

struct worker {
    int id;
    long long s, q;
};

struct comp {
    bool operator() (worker& a, worker& b) {
        return a.s*b.q < b.s*a.q;
    }
};

struct comp2 {
    bool operator() (worker& a, worker& b) {
        return a.q < b.q;
    }
};

int n, total=0, index=0, best=0;
long long w, t=0;
long double cost = 100000000000000000;

vector<worker> v;
priority_queue<worker, vector<worker>, comp2> pq;

void round(int num) {
    t += v[num-1].q;
    pq.push(v[num-1]);
    while (!pq.empty() && t*v[num-1].s > w*v[num-1].q) {
        t -= pq.top().q;
        pq.pop();
    }
    if (pq.size() > total || (pq.size()==total && (t*pq.top().s)/((double)pq.top().q) < cost+EPS)) {
        total = pq.size();
        cost = (t*pq.top().s)/((long double)pq.top().q);
        best = num;
    }
}

int main() {
    int s, q;
    scanf("%d%lld", &n, &w);
    for (int i=1; i<=n; i++) {
        scanf("%d%d", &s, &q);
        v.push_back({i, s, q});
    }
    sort(v.begin(), v.end(), comp());
    for (int i=1; i<=n; i++) round(i);
    printf("%d\n", total);
    while (!pq.empty()) pq.pop();
    t = 0;
    cost = 100000000000000000;
    for (int i=1; i<=best; i++) round(i);
    while (!pq.empty()) {
        printf("%d\n", pq.top().id);
        pq.pop();
    }
}

Compilation message (stderr)

hiring.cpp: In function 'void round(int)':
hiring.cpp:40:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<worker, std::vector<worker>, comp2>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if (pq.size() > total || (pq.size()==total && (t*pq.top().s)/((double)pq.top().q) < cost+EPS)) {
      |         ~~~~~~~~~~^~~~~~~
hiring.cpp:40:40: warning: comparison of integer expressions of different signedness: 'std::priority_queue<worker, std::vector<worker>, comp2>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if (pq.size() > total || (pq.size()==total && (t*pq.top().s)/((double)pq.top().q) < cost+EPS)) {
      |                               ~~~~~~~~~^~~~~~~
hiring.cpp: In function 'int main()':
hiring.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d%lld", &n, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%d%d", &s, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~

• 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