#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
vector<int> xs, ys;
vector<pair<int, int>> books(t);
for (int i = 0; i < a; i++) {
xs.push_back(x[i]);
}
for (int i = 0; i < b; i++) {
ys.push_back(y[i]);
}
for (int i = 0; i < t; i++) {
books[i] = make_pair(w[i], s[i]);
}
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
int mxx = (xs.empty()) ? INT_MIN : xs.back(), mxy = (ys.empty()) ? INT_MIN : ys.back();
for (int i = 0; i < t; i++) {
if (w[i] >= mxx && s[i] >= mxy) {
return -1;
}
}
vector<int> precalca(t, b), precalcb(t, a);
sort(books.rbegin(), books.rend());
for (int i = 0; i < t; i++) {
int lowpos = upper_bound(ys.begin(), ys.end(), books[i].second) - ys.begin();
precalca[i] = lowpos;
int lowwpos = upper_bound(xs.begin(), xs.end(), books[i].first) - xs.begin();
precalcb[i] = lowwpos;
}
auto ok = [&](int mid) {
vector<int> acx(a), acy(b);
set<int> not_full_indicesa, not_full_indicesb;
for (int i = 0; i < a; i++) {
not_full_indicesa.insert(i);
}
for (int i = 0; i < b; i++) {
not_full_indicesb.insert(i);
}
vector<bool> ass(t);
for (int i = 0; i < t; i++) {
auto it = not_full_indicesb.lower_bound(precalca[i]);
if (it != not_full_indicesb.end()) {
int k = *it;
++acy[k];
if (acy[k] == mid) {
not_full_indicesb.erase(it);
}
ass[i] = true;
}
}
for (int i = 0; i < t; i++) {
if (!ass[i]) {
auto it = not_full_indicesa.lower_bound(precalcb[i]);
if (it != not_full_indicesa.end()) {
int k = *it;
++acx[k];
if (acx[k] == mid) {
not_full_indicesa.erase(it);
}
ass[i] = true;
} else {
return false;
}
}
}
return true;
};
int lo = 1, hi = 1e6, ind = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (ok(mid)) {
ind = mid;
hi = mid - 1;
} else lo = mid + 1;
}
return ind;
}
