Submission #535802

#	Time	Username	Problem	Language	Result	Execution time	Memory
535802		bonk	Robots (IOI13_robots)	C++14	100 / 100	1706 ms	25912 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

bool check(vector<int>&weak, vector<int>&small, vector<pair<int, int>>&toys, int x){
    priority_queue<int>pq;
    priority_queue<int, vector<int>, greater<int>>pq2;

    int j = 0;
    for(int i = 0; i < weak.size(); i++){
        while(j < toys.size() && toys[j].first < weak[i]){
            pq.push(toys[j].second);    //push sizenya
            j++;
        }

        //angkat sebanyak x, angkat dari yg size terbesar spy kemungkinan small robots tdk bs angkat mengecil (?)
        //lesgo sotoy
        for(int k = 0; k < x; k++){ 
            if(pq.empty()) break;
            pq.pop();
        }
    }

    //pindahkan ke pq increasing?
    while(!pq.empty()){ 
        pq2.push(pq.top());
        pq.pop();
    }

    //sisa toys
    for(int i = j; i < toys.size(); i++) pq2.push(toys[i].second);

    for(int i = 0; i < small.size(); i++){
        if(pq2.empty()) return true;

        int cnt = 0;
        while(!pq2.empty() && pq2.top() < small[i] && cnt < x){
            pq2.pop();
            cnt++;
        }
    }

    if(pq2.empty()) return true;
    return false;
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]){
    vector<int>weak, small;
    vector<pair<int, int>>toys;

    for(int i = 0; i < a; i++) weak.push_back(x[i]);
    for(int i = 0; i < b; i++) small.push_back(y[i]);
    for(int i = 0; i < t; i++) toys.emplace_back(w[i], s[i]);

    sort(weak.begin(), weak.end());
    sort(small.begin(), small.end());
    sort(toys.begin(), toys.end());

    int ans = -1;
    int l = 0, r = t;

    while(l <= r){
        int mid = (l + r)/2;

        if(check(weak, small, toys, mid)){
            ans = mid;
            r = mid - 1;
        } else{
            l = mid + 1;
        }
    }

    return ans;
}

// int main(){
//     int a, b, t; cin >> a >> b >> t;
//     int x[a], y[b], w[t], s[t];

//     for(int i = 0; i < a; i++) cin >> x[i];
//     for(int i = 0; i < b; i++) cin >> y[i];
//     for(int i = 0; i < t; i++) cin >> w[i] >> s[i];

//     cout << putaway(a, b, t, x, y, w, s) << endl;

//     return 0;
// }

Compilation message (stderr)

robots.cpp: In function 'bool check(std::vector<int>&, std::vector<int>&, std::vector<std::pair<int, int> >&, int)':
robots.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < weak.size(); i++){
      |                    ~~^~~~~~~~~~~~~
robots.cpp:12:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         while(j < toys.size() && toys[j].first < weak[i]){
      |               ~~^~~~~~~~~~~~~
robots.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = j; i < toys.size(); i++) pq2.push(toys[i].second);
      |                    ~~^~~~~~~~~~~~~
robots.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0; i < small.size(); i++){
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10