Submission #1317868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317868		tsetsenbileg	Robots (IOI13_robots)	C++20	76 / 100	3094 ms	8364 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    // return 9;
    sort(X, X + A);
    sort(Y, Y + B);
    vector<pr> toy(T);
    for (int i = 0; i < T; i++) {
        toy[i] = {W[i], S[i]};
        bool can = false;
        for (int j = 0; j < A && !can; j++) if (X[j] > W[i]) can = true;
        for (int j = 0; j < B && !can; j++) if (Y[j] > S[i]) can = true;
        if (!can) return -1;
    }
    sort(toy.begin(), toy.end());
    int l = 0, r = T+1;
    while (l < r) {
        int m = (l + r) >> 1;
        bool good = 0;
        priority_queue<pr> sz;
        vector<bool> used(T, 0);
        for (int i = 0, j = 0; i < A; i++) {
            while (j < T && X[i] > toy[j].first) {
                sz.push({toy[j].second, j});
                j++;
            }
            for (int k = 0; k < m; k++) {
                if (sz.empty()) break;
                auto [s, p] = sz.top(); sz.pop();
                used[p] = 1;
            }
        }
        vector<int> unused;
        for (int i = 0; i < T; i++) {
            if (!used[i]) unused.pb(toy[i].second);
        }
        sort(unused.begin(), unused.end());
        for (int i = 0, j = 0; i < B; i++) {
            for (int k = 0; k < m; k++) {
                if (j < unused.size() && unused[j] < Y[i]) {
                    j++;
                }
                else break;
            }
            if (j == unused.size()) {
                good = 1;
                break;
            }
        }
        if (unused.empty()) good = 1;
        if (good) r = m;
        else l = m+1;
    }
    if (l == T+1) return -1;
    else return l;
}

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