#include "robots.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int A; //# weak robots
int B; //# small robots
int T; //# toys
int* W1;
int* S1;
struct toyW
{
int k;
};
bool operator < (toyW P, toyW Q)
{
if(W1[P.k] == W1[Q.k]) return P.k < Q.k;
return W1[P.k] < W1[Q.k];
}
struct toyS
{
int k;
};
bool operator < (toyS P, toyS Q)
{
if(S1[P.k] == S1[Q.k]) return P.k < Q.k;
return S1[P.k] < S1[Q.k];
}
set<toyW> TW_1;
set<toyW> TW1;
set<toyS> TS2;
// int binary_search(int a, int b, int X[], int Y[], int W[], int S[])
// {
// }
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[])
{
A = a;
sort(X, X+A, [] (int u, int v)
{
return u < v;
});
// cerr << "check\n";
B = b;
sort(Y, Y+B, [] (int u, int v)
{
return u < v;
});
// cerr << "check\n";
T = t;
W1 = &W[0];
S1 = &S[0];
for(int k = 0; k < T; k++)
{
if((A == 0 || W[k] >= X[A-1]) && (B == 0|| S[k] >= Y[B-1]))
return -1;
TW_1.insert(toyW{k});
}
// cerr << "checking\n";
// cerr << "check\n";
int lo = 1;
int hi = T;
while(1)
{
if(lo == hi) return lo;
TW1 = TW_1;
TS2.clear();
// cerr << "searching range " << a << ' ' << b << '\n';
int m = (lo+hi)/2; //The maximum capacity of any robot.
// for(int x: X) //weak robots
for(int q = 0; q < A; q++) {int x = X[q];
// cerr << "x = " << x << '\n';
while(!TW1.empty() && W[TW1.begin()->k] < x)
{
int k = TW1.begin()->k;
TW1.erase(toyW{k});
TS2.insert(toyS{k});
}
int ctr = 0;
while(!TS2.empty() && ctr < m)
{
ctr++;
int k = TS2.rbegin()->k;
TS2.erase(toyS{k});
}
}
while(!TW1.empty())
{
int k = TW1.rbegin()->k;
TW1.erase(toyW{k});
TS2.insert(toyS{k});
}
for(int z = 0; z < B; z++) {int y = Y[z]; //small robots
// cerr << "y = " << y << '\n';
int ctr = 0;
while(!TS2.empty() && S[TS2.begin()->k] < y && ctr < m)
{
ctr++;
TS2.erase(TS2.begin());
}
}
if(!TS2.empty())
lo = m+1;
else
hi = m;
}
}
