#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
pii flip(pii values)
{
return {values.second, values.first};
}
//IMPORTANT NOTE: The robot can carry the toy if its weight/size is STRICTLY LESS than the limit
bool query(int D, vector<int> (&x), vector<int> (&y), vector<pii> (&toys))
{
priority_queue<pii> toystash;
int A = x.size();
int B = y.size();
int toy_index = 0;
for (int i=0; i<A; i++)
{
//process the weak robots from weakest to strongest
while (x[i] > toys[toy_index].first)
{
toystash.push(flip(toys[toy_index]));
toy_index++;
}
int cleaned = 0;
while ((cleaned<D) and (!toystash.empty()))
{
toystash.pop();
cleaned++;
}
}
int total_toys = toys.size()-2;
while (toy_index<=total_toys)
{
toystash.push(flip(toys[toy_index]));
toy_index++;
}
for (int i=B-1; i>=0; i--)
{
//process the small robots from biggest to smallest, yes, reverse order from previous
int cleaned = 0;
while ((cleaned<D) and (!toystash.empty()))
{
pii next_toy = toystash.top();
if (next_toy.first < y[i])
{
toystash.pop();
cleaned++;
}
else
{
cleaned = D;
}
}
}
if (toystash.empty())
return 1;
return 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X+A);
sort(Y, Y+B);
vector<int> x;
vector<int> y;
x.reserve(A);
y.reserve(B);
for (int i=0; i<A; i++)
x.push_back(X[i]);
for (int i=0; i<B; i++)
y.push_back(Y[i]);
int max_weight = 0;
if (A)
max_weight = X[A-1];
int max_size = 0;
if (B)
max_size = Y[B-1];
vector<pii> toys;
toys.reserve(T+1);
for (int i=0; i<T; i++)
{
toys.push_back({W[i], S[i]});
if ((W[i]>=max_weight) and (S[i]>=max_size))
return -1;
}
sort(toys.begin(), toys.end());
toys.push_back({max_weight, max_size});//add an inaccessible toy to help the implementation
int lo = 1;
int hi = T;
while (lo!=hi)
{
int mid = (lo+hi)/2;
if (query(mid, x, y, toys))
hi = mid;
else
lo = mid+1;
}
return lo;
}
