#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int A, B, T;
vector<int> robotWT, robotSZ, toyWT, toySZ;
struct cmp {
bool operator()(const int a, const int b) const {
return toySZ[a] > toySZ[b];
}
};
bool check(int M) {
// cout << "M " << M << endl;
vector<bool> done(T);
multiset<int, cmp> top; // top K largest toys
vector<int> wt(T); iota(wt.begin(), wt.end(), 0);
sort(wt.begin(), wt.end(), [&](const int a, const int b) {return toyWT[a] < toyWT[b]; });
int i = 0, r = 0;
while(i < T && r < A) { // r: weak robots
if (toyWT[wt[i]] < robotWT[r]) {
// cout << "ADD " << wt[i] << endl;
top.insert(wt[i++]);
} else {
int k = M;
while(k-- && top.size()) {
done[*top.begin()] = true;
// cout << "DONE " << *top.begin() << ' ' << k << endl;
top.erase(top.begin());
}
r++;
}
}
int k = M;
while(k-- && top.size()) {
done[*top.begin()] = true;
// cout << "DONE " << *top.begin() << ' ' << k << endl;
top.erase(top.begin());
}
multiset<int> left;
for(int i = 0; i < T; i++) {
if (done[i]) continue;
left.insert(toySZ[i]);
}
for(int r = 0; r < B; r++) {
int k = M;
while(left.size() && k-- && *left.begin() < robotSZ[r]) {
left.erase(left.begin());
}
}
return left.empty();
}
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
A = a, B = b, T = t;
robotWT.resize(A), robotSZ.resize(B), toyWT.resize(T), toySZ.resize(T);
for(int i = 0; i < A; i++) robotWT[i] = X[i];
for(int i = 0; i < B; i++) robotSZ[i] = Y[i];
for(int i = 0; i < T; i++) toyWT[i] = W[i], toySZ[i] = S[i];
sort(robotWT.begin(), robotWT.end()), sort(robotSZ.begin(), robotSZ.end());
int l = 1, r = T+1;
while(l < r) {
int m = (l + r) / 2;
if (check(m)) r = m;
else l = m + 1;
}
return (l == T+1 ? -1 : l);
}
