oj.uz

Submission #221795

# Submission time Handle Problem Language Result Execution time Memory
221795 2020-04-11T07:51:31 Z patrikpavic2 Hiring (IOI09_hiring) C++17
100 / 100
 457 ms 17096 KB 
/**
* 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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 10 ms 640 KB Output is correct
14 Correct 13 ms 896 KB Output is correct
15 Correct 14 ms 896 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 18 ms 1016 KB Output is correct
5 Correct 36 ms 2296 KB Output is correct
6 Correct 256 ms 9832 KB Output is correct
7 Correct 342 ms 13896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4184 KB Output is correct
2 Correct 89 ms 4208 KB Output is correct
3 Correct 88 ms 4312 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 7148 KB Output is correct
2 Correct 148 ms 7148 KB Output is correct
3 Correct 141 ms 7148 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 15332 KB Output is correct
2 Correct 368 ms 15332 KB Output is correct
3 Correct 370 ms 15460 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 17096 KB Output is correct
2 Correct 457 ms 16988 KB Output is correct
3 Correct 415 ms 17004 KB Output is correct