#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 50010
vector<int> sizes[maxn];
vector<int> ys;
int a, b;
priority_queue<int> active;
bool check(int mid) {
while (active.size()) active.pop();
// priority_queue<int> active;
for (int i = 0; i < a; i++) {
for (int vv : sizes[i]) active.push(vv);
for (int j = 0; j < mid; j++) {
if (!active.size()) break;
active.pop();
}
}
for (int vv : sizes[a]) active.push(vv);
// // cout << mid << " interim size: " << active.size() << endl;
// for (int thing : active) {
// cout << " " << thing << endl;
// }
for (int cur : ys) {
//go in order, starting with cur
// cout << " ---- cur: " << cur << endl;
if (!active.size()) break;
for (int j = 0; j < mid; j++) {
if (!active.size()) break;
if (active.top() >= cur) return false;
active.pop();
}
}
return active.size() == 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int lo = 1, hi = T;
//X is weight limits for A type robots
//Y is size limits for B type robogts
//limits cannot be equal
a = A;
b = B;
sort(X, X+A);
sort(Y, Y+B);
// cout << "Array of A" << endl;
// cout << " ";
// for (int i = 0; i < A; i++) cout << X[i] << " ";
// cout << endl;
for (int i = 0; i < B; i++) ys.push_back(Y[i]);
reverse(ys.begin(), ys.end());
for (int i = 0; i < T; i++) {
if ((A == 0 || W[i] >= X[A-1]) &&
(B == 0 || S[i] >= Y[B-1])) {
return -1;
}
//push back to largest A
int cw = W[i];
int cs = S[i];
int cl = 0;
int ch = A-1;
//manually doing the binary search thing
//find first guy this works for
if (A == 0 || cw >= X[A-1]) {
// cout <<"--> " << cw << " " << cs << " " << A << endl;
sizes[A].push_back(cs);
}
else {
while (cl < ch) {
int mid = (cl+ch)/2;
if (X[mid] > cw) {
//this spot works
ch = mid;
}
else cl = mid+1; //does not work for this value
}
// cout << "--> " << cw << " " << cs << " " << cl << endl;
sizes[cl].push_back(cs);
}
}
while (lo < hi) {
int mid = (lo+hi)/2;
if (check(mid)) {
// cout << "something worked" << endl;
hi = mid;
}
else lo = mid+1;
}
return lo;
}
