Submission #1075445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075445		Ignut	Robots (IOI13_robots)	C++17	90 / 100	3018 ms	22612 KiB

robots

// Ignut

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

using namespace std;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    pair<int, int> p[T];
    for (int i = 0; i < T; i ++) p[i] = {W[i], S[i]};
    sort(p, p + T);
    // for (int i = 0; i < T; i ++) cout << S[i] << '_' << W[i] << ' ';
    // cout << '\n';

    for (int i = 0; i < A; i ++) X[i] --;
    for (int i = 0; i < B; i ++) Y[i] --;
    sort(X, X + A);

    auto Check = [&](int k) -> bool {
        // cout << k << " : ";
        multiset<pair<int, int>> mw;
        for (int i = 0; i < B; i ++) mw.insert({Y[i], k});
        int cntX = k, indX = A - 1;
        for (int i = T - 1; i >= 0; i --) {
            auto it = mw.lower_bound({p[i].second, -1});
            if (it != mw.end()) {
                auto [u, v] = *it; mw.erase(it);
                v --;
                if (v > 0) mw.insert({u, v});
                // cout << "1";
                continue;
            }
            if (indX == -1)
                return false;
            if (X[indX] < p[i].first)
                return false;
            cntX --;
            if (cntX == 0) {
                cntX = k;
                indX --;
            }
            // cout << "0";
        }
        // cout << '\n';
        return true;
    };

    int lo = 1, hi = T + 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        bool ch = Check(mid);
        if (!ch) cout << '\n';
        if (ch)
            hi = mid;
        else
            lo = mid + 1;
    }

    if (lo == T + 1) return -1;
    return lo;
}

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