Submission #1214777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214777		gustavo_d	Robots (IOI13_robots)	C++20	76 / 100	3094 ms	31928 KiB

robots

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

const int MAXT = 1e6;

pair<int, int> tasks[MAXT];

int putaway(
    int nWorker1, int nWorker2, int nTasks,
    int worker1[], int worker2[],
    int task1[], int task2[]
) {
    sort(worker1, worker1+nWorker1);
    sort(worker2, worker2+nWorker2);

    if (nWorker1 < nWorker2) {
        swap(nWorker1, nWorker2);
        swap(worker1, worker2);
        swap(task1, task2);
    }

    for (int t=0; t<nTasks; t++)
        tasks[t] = {task1[t], task2[t]};

    sort(tasks, tasks + nTasks);
    int l = 1, r = nTasks; int ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;

        // cout << "check" << mid << endl;

        bool check = true;
        vector<bool> done(nTasks, false);
        int pt = nTasks-1;
        for (int w1=nWorker1-1; w1>=0; w1--) {
            // cout << "worker1 (" << w1 << "): ";
            int k = mid;
            while (pt >= 0 and tasks[pt].first >= worker1[w1]) pt--;
            while (k > 0 and pt >= 0) {
                k--;
                // cout << pt << ' ';
                done[pt--] = true;
            }
            // cout << endl;
        }

        set<pair<int, int>> w2;
        vector<int> qty2(nWorker2, mid - 1);
        for (int i=0; i<nWorker2; i++) {
            w2.insert({worker2[i], i});
        }

        multiset<int> t2;
        for (int t=nTasks-1; t>=0; t--) {
            t2.insert(tasks[t].second);
            if (done[t])
                continue;
            // cout << "task " << t << ':' << *t2.begin() << ' ';
            auto it = upper_bound(w2.begin(), w2.end(), make_pair(*t2.begin(), 10000000));
            if (it == w2.end()) {
                // cout << "falhou" << endl;
                check = false;
                break;
            }
            // cout << it->first << endl;
            if (qty2[it->second] > 0) {
                qty2[it->second]--;
            } else w2.erase(it);
            t2.erase(t2.begin());
        }

        // cout << endl << endl;

        if (check) {
            ans = mid;
            r = mid-1;
        } else l = mid+1;
    }
    return ans;
}

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