#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
namespace r = ranges;
namespace v = ranges::views;
// has to return toys sorted in decreasing y
vector<pair<int, int>> remove_one_dim(const vector<pair<int, int>> &toys,
const vector<int> &limits,
int toys_per_bot) {
int ctoy = 0;
// toys are sorted by increasing weight
priority_queue<pair<int, int>>
remaining_toys; // toys here are stored in (y, x) order
for (int weight_limit : limits) {
while (ctoy < toys.size() && toys[ctoy].first < weight_limit) {
auto toy = toys[ctoy++];
remaining_toys.emplace(toy.second, toy.first);
}
for (int i = 0; i < toys_per_bot && !remaining_toys.empty(); ++i) {
/*auto [y, x] = remaining_toys.top();*/
/*cerr << "weight limit " << weight_limit << " to toy " << x << " " << y
* << endl;*/
remaining_toys.pop();
}
}
while (ctoy < toys.size()) {
auto toy = toys[ctoy++];
remaining_toys.emplace(toy.second, toy.first);
}
vector<pair<int, int>> ans;
while (!remaining_toys.empty()) {
auto [y, x] = remaining_toys.top();
remaining_toys.pop();
ans.emplace_back(x, y);
}
return ans;
}
template <typename R> vector<r::range_value_t<R>> vec_of(R &&range) {
return vector(range.begin(), range.end());
}
bool can_put_away(const vector<pair<int, int>> &compressed_toys, int A, int B, int toys_per_bot) {
cerr << "CPA == " << endl;
vector<int> layers =
vec_of(compressed_toys | v::transform([&](pair<int, int> p) {
return max(A - p.first, B - p.second);
}));
r::sort(layers);
int pending = 0, ctoy = 0;
for (int clayer = 0; clayer <= max(A, B); ++clayer) {
while (ctoy < layers.size() && layers[ctoy] <= clayer) {
++pending; ++ctoy;
}
// how many bots can we clear at this layer?
// at layer 0, there are no bots
// at layer 1...min(A, B), we have one horizontal and one vertical bot
// at all other layers we only have one other bot
int clearable = (clayer == 0 ? 0 : clayer <= min(A, B) ? 2 * toys_per_bot : toys_per_bot);
pending -= clearable;
if (pending > 0) return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vector<int> weight_limits(X, X + A);
vector<int> size_limits(Y, Y + B);
r::sort(weight_limits);
r::sort(size_limits);
// where is my ranges::to bwaaaaaaaaa
vector<pair<int, int>> toys = vec_of(
v::iota(0, T) | v::transform([&](int i) { return pair{W[i], S[i]}; }));
vector<pair<int, int>> compressed_toys = vec_of(
toys | v::transform([&](pair<int, int> p) {
return pair{(int)distance(weight_limits.begin(),
r::upper_bound(weight_limits, p.first)),
(int)distance(size_limits.begin(),
r::upper_bound(size_limits, p.second))};
}));
if (!can_put_away(compressed_toys, A, B, T))
return -1;
int lo = 1, hi = T;
while (lo < hi) {
int mid = (lo + hi) / 2;
/*cerr << "try " << mid << endl;*/
if (can_put_away(compressed_toys, A, B, mid))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
