Submission #1214762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214762		gustavo_d	Robots (IOI13_robots)	C++20	76 / 100	3095 ms	31912 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;
        }

        multiset<int> w2;
        int cnt = 0, k = 0; pt=nWorker2;
        while (cnt < nTasks and pt >= 0) {
            if (k == 0) {
                k = mid;
                pt--;
                continue;
            }
            k--;
            w2.insert(worker2[pt]);
            cnt++;
        }

        // cout << "workers2: ";
        // for (int v : w2) cout << v << ' ';
        // cout << endl;

        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(), *t2.begin());
            if (it == w2.end()) {
                // cout << "falhou" << endl;
                check = false;
                break;
            }
            // cout << *it << endl;
            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