Submission #592956

#	Time	Username	Problem	Language	Result	Execution time	Memory
592956		stevancv	Robots (IOI13_robots)	C++14	100 / 100	1783 ms	18524 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int mod = 1e9 + 7;
int putaway(int p, int q, int n, int x[], int y[], int a[], int b[]) {
    vector<array<int, 2>> all;
    for (int i = 0; i < n; i++) {
        all.push_back({a[i], b[i]});
    }
    for (int i = 0; i < p; i++) x[i]--;
    for (int i = 0; i < q; i++) y[i]--;
    sort(all.begin(), all.end());
    sort(x, x + p);
    sort(y, y + q);
    auto Can = [&] (int o) {
        vector<bool> cov(n);
        priority_queue<array<int, 2>> pq;
        int j = 0;
        for (int i = 0; i < p; i++) {
            while (j < n && all[j][0] <= x[i]) {
                pq.push({all[j][1], j});
                j++;
            }
            int cnt = 0;
            while (!pq.empty() && cnt < o) {
                auto w = pq.top();
                cov[w[1]] = 1;
                pq.pop();
                cnt++;
            }
        }
        vector<int> c;
        for (int i = 0; i < n; i++) {
            if (!cov[i]) c.push_back(all[i][1]);
        }
        sort(c.begin(), c.end());
        j = 0;
        for (int i = 0; i < q; i++) {
            int cnt = 0;
            while (j < c.size() && c[j] <= y[i] && cnt < o) {
                j++;
                cnt++;
            }
        }
        if (j == c.size()) return true;
        return false;
    };
    int l = 1; int r = n;
    int ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (Can(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    return ans;
}

Compilation message (stderr)

robots.cpp: In lambda function:
robots.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             while (j < c.size() && c[j] <= y[i] && cnt < o) {
      |                    ~~^~~~~~~~~~
robots.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if (j == c.size()) return true;
      |             ~~^~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~

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