Submission #1076129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076129		mc061	Robots (IOI13_robots)	C++17	100 / 100	1696 ms	37828 KiB

robots

#pragma once
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;

template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for (int i = 0; i < A; ++i) --X[i];
    for (int i = 0; i < B; ++i) --Y[i];
    sort(X, X+A);
    sort(Y, Y+B);
    vector<pair<int, int>> qs;
    for (int i = 0; i < T; ++i) {
        qs.push_back({W[i], S[i]});
        if (W[i] > X[A-1] && S[i] > Y[B-1]) return -1;
    }
    sort(qs.begin(), qs.end());
    
    //each robot takes at most k
    auto check = [&] (int k) -> bool {
        vector<int> to_y;
        vector<vector<pair<int, int>>> to_x(A);
        for (int i = 0; i < T; ++i) {
            auto it = lower_bound(X, X+A, W[i]);
            if (it == X+A) {
                to_y.push_back(S[i]);
                continue;
            }
            to_x[it-X].push_back({W[i], S[i]});
        }
        minheap<pair<int, int>> pq;
        int cnt = 1;
        for (int i = A-1; i >= 0; --i, ++cnt) { 
            for (auto [w, s] : to_x[i]) {
                pq.push({s, w});
            }
            while (cnt * k < pq.size()) {
                to_y.push_back(pq.top().first);
                pq.pop();
            }
        }
        sort(to_y.begin(), to_y.end());
        vector<int> cntb(B, 0);
        int ptr = 0;
        for (int i = 0; i < to_y.size(); ++i) {
            while (ptr < B && (cntb[ptr] == k || Y[ptr] < to_y[i])) ++ptr;
            if (ptr == B) return false;
            cntb[ptr]++;
        }
        return true;
    };
    
    int low = 0, high = T+1;
    while (high - low > 1) {
        int mid = (high + low) >> 1;
        if (check(mid)) high = mid;
        else low = mid;
    }
    return high;
}

Compilation message (stderr)

robots.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
robots.cpp: In lambda function:
robots.cpp:39:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             while (cnt * k < pq.size()) {
      |                    ~~~~~~~~^~~~~~~~~~~
robots.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < to_y.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~

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