Submission #1059073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059073		oscarsierra12	Robots (IOI13_robots)	C++14	100 / 100	683 ms	28380 KiB

robots

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

using namespace std;

#define ff first
#define ss second
#define pb push_back


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

const ll N = 110;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort (X, X + A);
    sort (Y, Y + B);

    vector <pii> ws(T);
    for (int i = 0; i < T; ++i) ws[i] = {W[i], S[i]};
    sort (ws.begin(), ws.end());

    int lw = 1, hg = T + 1;
    while (lw < hg) { 
        int mi = (lw + hg) / 2;

        int idx = A - 1;
        int can = 1;

        priority_queue <int, vector<int>, greater<int>> pq;
        vector <int> siz;

        for (int i = T - 1; i >= 0; --i) { 
            pq.push (ws[i].ss);
            while (idx >= 0 && X[idx] > ws[i].ff) idx--;

            while (pq.size() && pq.size() > 1ll * (A - 1 - idx) * mi) {
                siz.pb(pq.top()); 
                pq.pop();
            }
        }

        sort (siz.begin(), siz.end());
        int sz = siz.size();
        idx = B - 1;
        vector <int> use (B, 0);

        if (idx < 0 && siz.size() > 0) can = 0;
 
        for (int i = sz - 1; i >= 0; --i) { 
            while (idx >= 0 && (use[idx] == mi || Y[idx] <= siz[i])) idx--;
            if (idx < 0) {
                can = 0;
                break;
            }
            use[idx]++;
        }
 
        if (can) hg = mi;
        else lw = mi + 1;
    }
    if (lw == T + 1) return -1;
    return hg;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:38:43: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |             while (pq.size() && pq.size() > 1ll * (A - 1 - idx) * mi) {
      |                                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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