Submission #221795

#	Time	Username	Problem	Language	Result	Execution time	Memory
221795		patrikpavic2	Hiring (IOI09_hiring)	C++17	100 / 100	457 ms	17096 KiB

hiring

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  hiring
* score: 100.0
* date:  2019-05-11 08:41:56.644498
*/
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>


#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;

const int N = 5e5 + 500;

int Q[N], A[N], p[N], n, ans = 0, rmb;
ll W;
long double WW;
priority_queue < int > s;
priority_queue < pii > s2;

bool cmp(int i,int j){
    return A[i] * Q[j] < A[j] * Q[i];
}

int main(){
    scanf("%d%lld", &n, &W);
    for(int i = 0;i < n;i++)
        p[i] = i, scanf("%d%d", A + i, Q + i);
    sort(p, p + n, cmp); ll sm = 0;
    for(int ii = 0;ii < n;ii++){
        int i = p[ii];
        s.push(Q[i]); sm += Q[i];
        for(;sm * A[i] > W * Q[i]; sm -= s.top(), s.pop());
        if(((int)s.size() > ans) || ((long double) sm * A[i] < WW * Q[i] && (int)s.size() == ans)){
            ans = (int)s.size();
            WW = (long double) sm * A[i] / Q[i];
            rmb = ii;
        }
       // printf("S %d\n", s.size());
    }
    //printf("kurac %d %d\n", ans, rmb);
    sm = 0;
    for(int i = 0;i <= rmb;i++) s2.push({Q[p[i]], p[i]}), sm += Q[p[i]];
    rmb = p[rmb];
    for(;sm * A[rmb] > W * Q[rmb]; sm -= s2.top().X, s2.pop());
    printf("%d\n", s2.size());
    for(;s2.size() > 0;s2.pop()) printf("%d\n", s2.top().Y + 1);
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:57:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::priority_queue<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", s2.size());
                    ~~~~~~~~~^
hiring.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld", &n, &W);
     ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         p[i] = i, scanf("%d%d", A + i, Q + i);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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