#include "robots.h"
#include <cassert>
#include <algorithm>
#include <map>
#include <vector>
#include <numeric>
#include <functional>
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
std::sort(X, X+A);
std::sort(Y, Y+B);
for(int i=0;i<T;++i)
if((A==0||W[i]>=X[A-1]) && (B==0||S[i]>=Y[B-1]))
return -1;
for(int i=0;i<T;++i)
{
W[i] = A?std::lower_bound(X, X+A, W[i]+1)-X:0;
assert(0 <= W[i] && W[i] <= A);
S[i] = B?std::lower_bound(Y, Y+B, S[i]+1)-Y:0;
assert(0 <= S[i] && S[i] <= B);
}
//must be possible;
std::vector<int> ord(T);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int u, int v){return W[u]<W[v];});
int l=0, r=T;
for(;r-l>1;)
{
int m=l+(r-l)/2;
int j=0;
std::map<int, int> map;
for(int i=0;i<=A;++i)
{
for(;j < T && W[ord[j]] == i;++j)
++map[S[ord[j]]];
if(i<A)
for(int rem=m;rem>0 && !map.empty();)
{
auto it=std::prev(map.end());
if(rem >= it->second)
rem -= it->second, map.erase(it);
else
it->second -= rem, rem=0;
}
}
assert(j == T);
int c=0;
for(int i=0;i<=B;++i)
{
if(!map.empty() && map.begin()->first == i)
c += map.begin()->second, map.erase(map.begin());
if(i<B)
c=std::max(c-m, 0);
}
if(c==0) // good
r=m;
else
l=m;
}
return r;
}
