#include "robots.h"
#include <algorithm>
#include <functional>
#include <ranges>
#include <vector>
#include <cassert>
using namespace std;
/* We order all the robots in a single sequence as follows: All the weak
* robots in *increasing* order of their weight limits, followed by all
* the small robots in *decreasing* order of their size limits. This way,
* for each toy, if one looks at the set of robots which can pick up that
* toy, it forms a contiguous subinterval of the sequence of all robots.
*
* At this point, one can rephrase the problem as follows: You are given T
* subintervals of [0,N) (where N = A + B). For each such interval, you
* have to choose an integer point in it as its chosen point. For each i
* in [0, N), the weight of i is the number of intervals for which it has
* been chosen. Choose points to minimize the maximum weight of all elements
* of [0, N). Note that in this formulation we don't reference any of the
* weight or size limits, and we don't make distinction between weak and
* small robots.
*/
// Interval of integers [L, U).
struct Interval {
int L, U;
inline int length() const { return U-L; }
};
bool possible(const vector<vector<int>> &ends, int limit);
int solveForIntervals(vector<Interval> intervals, int N) {
// each interval is a subinterval of [0,N).
// Consider all intervals whose beginning is i. The multiset
// of all their ends is ends[i].
vector<vector<int>> ends(N);
for(Interval ivl : intervals) {
ends[ivl.L].push_back(ivl.U);
}
// answer is the smallest limit for which possible(ends, limit) is true.
// Invariant: answer is in (L, U].
// ****NOTE**** Rare use of left-open right-closed intervals!
int L = 0, U = intervals.size();
while(U-L > 1) {
int mid = L + (U-L)/2;
//ez::println("possible ", mid, " ", foo);
if(possible(ends, mid)) {
U = mid;
} else {
L = mid;
}
}
return U;
}
vector<int> heapOfEnds; // Min heap, so need to use greater()
bool possible(const vector<vector<int>> &ends, int limit) {
heapOfEnds.reserve(ends.size());
heapOfEnds.resize(0);
for(int b : views::iota(int(0), int(ends.size()))) {
// Looking at all intervals which begin with b.
// Their endpoints are ends[b]. We add them all
// into consideration, and then take away at most
// limit of them - for these intervals, we choose b
// as their chosen point.
for(int end : ends[b]) {
heapOfEnds.push_back(end);
push_heap(heapOfEnds.begin(), heapOfEnds.end(), greater());
}
for(int i=0; i<limit && !heapOfEnds.empty(); ++i) {
pop_heap(heapOfEnds.begin(), heapOfEnds.end(), greater());
if(heapOfEnds.back() <= b) {
// We have an interval ending at heapOfEnds.back(),
// but we haven't been able to choose a point in it, and it is
// too late now, as we are past the end.
return false;
}
heapOfEnds.pop_back();
}
}
return heapOfEnds.empty();
}
/* A: number of weak robots.
* B: number of small robots.
* T: number of toys.
* X: array of length A, weight limits of weak robots.
* Y: array of length B, size limits of small robots.
* W: array of length T, weight of each toy.
* S: array of length T, size of each toy.
*/
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X+A, less()); // weak robots in increasing order of weight limits.
sort(Y, Y+B, greater()); // small robots in decreasing order of size limits.
vector<Interval> intervals;
intervals.reserve(T);
for(int t : views::iota(0,T)) {
Interval ivl {
int(upper_bound(X, X+A, W[t], less()) - X),
int(A + (lower_bound(Y, Y+B, S[t], greater()) - Y))
};
assert(ivl.length() >= 0);
if(ivl.length() == 0) {
return -1;
}
intervals.push_back(ivl);
}
return solveForIntervals(intervals, A+B);
}
