#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(), 0));
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |