Submission #1317872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317872		tsetsenbileg	Robots (IOI13_robots)	C++20	14 / 100	3095 ms	16036 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<array<int, 3>> toy(T), tox(T);
    for (int i = 0; i < T; i++) {
        toy[i] = {W[i], S[i], i};
        tox[i] = {W[i], S[i], 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());
    sort(tox.begin(), tox.end(), [](const array<int, 3>& x, const array<int, 3>& y) {
        return x[1] < y[1];
    });
    vector<int> where(T);
    for (int i = 0; i < T; i++) {
        where[tox[i][2]] = i;
    }
    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][0]) {
                sz.push({toy[j][1], 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(tox[where[toy[i][2]]][1]);
        }
        //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: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10