#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> T_W1;
set<toyS> T_S1;
set<toyW> TW1, TW2;
set<toyS> TS1, TS2;
int binary_search(int a, int b, int X[], int Y[], int W[], int S[])
{
if(a == b) return a;
TW1 = T_W1;
TW2.clear();
TS1 = T_S1;
TS2.clear();
// cerr << "searching range " << a << ' ' << b << '\n';
int m = (a+b)/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});
TS1.erase(toyS{k});
TW2.insert(toyW{k});
TS2.insert(toyS{k});
}
int ctr = 0;
while(!TS2.empty() && ctr < m)
{
ctr++;
int k = TS2.rbegin()->k;
TS2.erase(toyS{k});
TW2.erase(toyW{k});
}
}
while(!TW1.empty())
{
int k = TW1.rbegin()->k;
TW1.erase(toyW{k});
TS1.erase(toyS{k});
TW2.insert(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())
return binary_search(m+1, b, X, Y, W, S);
else
return binary_search(a, m, X, Y, W, 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;
}
// cerr << "checking\n";
// cerr << "check\n";
for(int k = 0; k < T; k++)
{
T_W1.insert(toyW{k});
T_S1.insert(toyS{k});
}
return binary_search(1, T, X, Y, W, S);
}
