Submission #1081458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081458		Gray	Robots (IOI13_robots)	C++17	76 / 100	2328 ms	41900 KiB

robots

#pragma GCC optimize("O3")
#include "robots.h"

#include <bits/stdc++.h>

#define ll int
#define ff first
#define ss second

using namespace std;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    ll weak[A], small[B];
    pair<ll, ll> toy[T];

    // Copy input arrays to local variables
    memcpy(weak, X, A * sizeof(ll));
    memcpy(small, Y, B * sizeof(ll));
    for (ll i = 0; i < T; i++) {
        toy[i] = {W[i], S[i]};
    }

    // Sort in decreasing order
    sort(weak, weak + A, greater<ll>());
    sort(small, small + B, greater<ll>());
    sort(toy, toy + T, greater<pair<ll, ll>>());

    vector<ll> slot_small;
    set<pair<ll, ll>> cand;
    ll lo = 0, hi = T + 1;
    bool upos = false;

    while (lo + 1 < hi) {
        ll x = lo + (hi - lo) / 2;
        bool pos = true;
        slot_small.clear();
        cand.clear();
        ll l = 0, free_robot = 0;

        for (ll i = 0; i < T; i++) {
            while (l < A && weak[l] > toy[i].ff) {
                l++;
                free_robot = min(free_robot + x, INT_MAX);
            }
            cand.insert({toy[i].ss, i});
            if (free_robot > 0) {
                free_robot--;
            } else {
                slot_small.push_back(cand.begin()->ss);
                cand.erase(cand.begin());
            }
        }

        sort(slot_small.rbegin(), slot_small.rend(), [&](ll op1, ll op2) {
            return toy[op1].ss < toy[op2].ss;
        });

        l = 0;
        free_robot = 0;
        for (ll i = 0; i < (ll)(slot_small.size()); i++) {
            while (l < B && small[l] > toy[slot_small[i]].ss) {
                free_robot += x;
                l++;
            }
            if (free_robot == 0) {
                pos = false;
                break;
            }
            free_robot--;
        }

        if (pos) {
            hi = x;
            upos = true;
        } else {
            lo = x;
        }
    }

    return upos ? hi : -1;
}

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