#include "robots.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int A; //# weak robots
vector<int> X;
int B; //# small robots
vector<int> Y;
int T; //# toys
vector<int> W;
vector<int> S;
struct toyW
{
int k;
};
bool operator < (toyW P, toyW Q)
{
if(W[P.k] == W[Q.k]) return P.k < Q.k;
return W[P.k] < W[Q.k];
}
struct toyS
{
int k;
};
bool operator < (toyS P, toyS Q)
{
if(S[P.k] == S[Q.k]) return P.k < Q.k;
return S[P.k] < S[Q.k];
}
set<toyW> TW1, TW2;
set<toyS> TS1, TS2;
int binary_search(int a, int b)
{
TW1.clear();
TW2.clear();
TS1.clear();
TS2.clear();
if(a == b) return a;
// cerr << "searching range " << a << ' ' << b << '\n';
int m = (a+b)/2; //The maximum capacity of any robot.
for(int k = 0; k < T; k++)
{
TW1.insert(toyW{k});
TS1.insert(toyS{k});
}
for(int x: X) //weak robots
{
// 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 y: Y) //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);
else
return binary_search(a, m);
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
A = a;
X = vector<int>(A);
for(int i = 0; i < A; i++) X[i] = x[i];
sort(X.begin(), X.end(), [] (int u, int v)
{
return u < v;
});
// cerr << "check\n";
B = b;
Y = vector<int>(B);
for(int j = 0; j < B; j++) Y[j] = y[j];
sort(Y.begin(), Y.end(), [] (int u, int v)
{
return u < v;
});
// cerr << "check\n";
T = t;
W = S = vector<int>(T);
for(int k = 0; k < T; k++)
{
W[k] = w[k];
S[k] = s[k];
// cerr << "k = " << k << '\n';
if((X.empty() || W[k] >= X.back()) && (Y.empty() || S[k] >= Y.back()))
return -1;
}
// cerr << "checking\n";
// cerr << "check\n";
return binary_search(1, T);
}
