#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
bool canPut(int TIME, int A, int B, int T, vector< vector<int> >& WeakRobot, int Y[], int S[]) {
priority_queue<int> maxSize;
for (int i = 0; i < A; ++i) {
int sz = WeakRobot[i].size();
if (TIME < sz) {
for (int j = TIME; j < sz; ++j) {
maxSize.push(S[WeakRobot[i][j]]);
// cerr << "+ " << S[WeakRobot[i][j]] << endl;
}
} else {
while (sz < TIME && !maxSize.empty()) {
++sz;
// cerr << "- " << maxSize.top() << endl;
maxSize.pop();
}
}
}
for (int val : WeakRobot[A]) maxSize.push(S[val]);
int i = B - 1, sz = maxSize.size();
while (i >= 0 && sz) {
// cerr << i << ' ' << sz << endl;
int j = min(sz, TIME);
// cerr << "Small Robot " << i << endl;
sz -= j;
while (j--) {
// cerr << maxSize.top() << ' ';
if (maxSize.top() > Y[i]) return false;
maxSize.pop();
}
// cerr << endl;
--i;
}
return (sz == 0);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X + A);
sort(Y, Y + B);
vector< vector<int> > WeakRobot(A + 1);
for (int i = 0; i < T; ++i) {
++W[i], ++S[i];
int idW = lower_bound(X, X + A, W[i]) - X;
WeakRobot[idW].push_back(i);
}
for (int i = 0; i < A; ++i) {
sort(WeakRobot[i].begin(), WeakRobot[i].end(), [&](int x, int y) {
return S[x] > S[y];
});
}
/*
for (int i = 0; i <= A; ++i) {
cerr << "WeakRobot " << i << endl;
for (int val : WeakRobot[i]) cerr << S[val] << ' '; cerr << endl;
}
*/
int l = 1, r = T;
int ans = -1;
while (l <= r) {
int m = (l + r) >> 1;
if (canPut(m, A, B, T, WeakRobot, Y, S)) {
ans = m;
r = m - 1;
} else l = m + 1;
}
return ans;
}
