#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define F(i, n) for(int i = 0; i < (n); i++)
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
using state = tuple<int, int, int>;
sort(X, X + A);
sort(Y, Y + B);
set<state> by_weight;
F(i, T) {
by_weight.emplace(W[i], S[i], i);
//by_size.emplace(S[i], W[i], i);
}
auto solver = [&](int num_per_robot) {
priority_queue<pair<int, int>> pq;
vector<bool> taken;
auto it = by_weight.begin();
F(i, A) {
int robot_weight_limit = X[i];
while(it != by_weight.end() && get<0>(*it) < robot_weight_limit) {
pq.emplace(get<1>(*it), get<2>(*it));
++it;
}
int cnt = num_per_robot;
while(!pq.empty() && cnt > 0) {
auto [sz, idx] = pq.top();
pq.pop();
cnt--;
}
}
multiset<int> by_size;
multiset<int> robots;
while(!pq.empty()) {
auto [_, idx] = pq.top();
pq.pop();
by_size.emplace(S[idx]);
}
while(it != by_weight.end()) {
by_size.emplace(get<1>(*it));
++it;
}
F(i, B) {
robots.emplace(Y[i]);
}
int cnt = num_per_robot;
while(cnt > 0 && !robots.empty()) {
vector<int> remove_list;
for(int robot_size_limit : robots) {
auto it = by_size.lower_bound(robot_size_limit);
if(it != by_size.begin()) {
--it;
by_size.extract(it);
} else {
remove_list.push_back(robot_size_limit);
break;
}
}
for(int rem : remove_list) {
robots.erase(rem);
}
cnt--;
}
//cout << num_per_robot << " solver return " << (pq2.empty()) << " " << (it2 == by_size.end()) << " " << by_size.size() << endl;
return by_size.empty();
};
int l = 1, r = T;
while(l <= r) {
int m = (l + r) / 2;
if(solver(m)) {
r = m - 1;
} else {
l = m + 1;
}
}
if(!solver(l)) {
return -1;
}
return l;
};
