#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
namespace r = ranges;
namespace v = ranges::views;
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<int> &layers, int A, int B, int toys_per_bot) {
long long 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));
// allow pending to go negative, to allow bots here to put away bots we discover later on
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))};
}));
vector<int> layers =
vec_of(compressed_toys | v::transform([&](pair<int, int> p) {
return max(A - p.first, B - p.second);
}));
r::sort(layers);
if (!can_put_away(layers, 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(layers, A, B, mid))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |