#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
namespace r = ranges;
namespace v = ranges::views;
vector<pair<int, int>> remove_one_dim(vector<pair<int, int>> toys,
const vector<int> &limits,
int toys_per_bot) {
int ctoy = 0;
r::sort(toys);
// 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 : v::iota(0, toys_per_bot)) {
if (remaining_toys.empty())
break;
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);
}
toys.clear();
while (!remaining_toys.empty()) {
auto [y, x] = remaining_toys.top();
remaining_toys.pop();
toys.emplace_back(x, y);
}
return toys;
}
bool can_put_away(const vector<pair<int, int>> &toys,
const vector<int> &weight_limits,
const vector<int> &size_limits, int toys_per_bot) {
auto remaining_toys = remove_one_dim(toys, weight_limits, toys_per_bot);
vector<pair<int, int>> other_dim;
for (auto [x, y] : remaining_toys)
other_dim.emplace_back(y, 1);
for (int l : size_limits)
other_dim.emplace_back(l, -1);
r::sort(other_dim);
int remaining_count = 0;
for (auto [y, evt] : other_dim) {
if (evt == -1) {
/*cerr << "! robot " << y << endl;*/
remaining_count = max(remaining_count - toys_per_bot, 0);
} else {
/*cerr << "! toy " << y << endl;*/
remaining_count++;
}
}
/*cerr << remaining_count << " toys remaining " << endl;*/
return remaining_count == 0;
}
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
auto _toys =
v::iota(0, T) | v::transform([&](int i) { return pair{W[i], S[i]}; });
vector<pair<int, int>> toys(_toys.begin(), _toys.end());
if (!can_put_away(toys, weight_limits, size_limits, T))
return -1;
int lo = 1, hi = T;
while (lo < hi) {
int mid = (lo + hi) / 2;
/*cerr << "try " << mid << endl;*/
if (can_put_away(toys, weight_limits, size_limits, mid))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
