#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int binsearch(int target, vector<int> (&arr))
{
int lo = 0;
int hi = arr.size()-1;
if (hi==-1)
return 0;
if (target>=arr[hi])
return hi+1;
while (lo!=hi)
{
int mid = (lo+hi)/2;
if (arr[mid]>target)
hi = mid;
else
lo = mid+1;
}
return lo;
}
int cel(int a, int b)//ceiling division
{
if (a==0)
return 0;
return ((a-1)/b)+1;
}
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<int> x;
vector<int> y;
x.reserve(A);
y.reserve(B);
for (int i=0; i<A; i++)
x.push_back(X[i]);
for (int i=0; i<B; i++)
y.push_back(Y[i]);
vector<vector<int>> matrix(A+1, vector<int> (B+1, 0));
for (int i=0; i<T; i++)
{
int r = binsearch(W[i], x);
int c = binsearch(S[i], y);
//cout << "toy at row " << r << '\n';
matrix[r][c]++;
}
//cout << matrix[0][0] << matrix[1][0] << matrix[2][0] << matrix[3][0] << " balala\n";
for (int i=A; i>=0; i--)
for (int j=B; j>=0; j--)
{
if (i!=A)
matrix[i][j] = matrix[i][j]+matrix[i+1][j];
}
for (int i=A; i>=0; i--)
for (int j=B; j>=0; j--)
{
if (j!=B)
matrix[i][j] = matrix[i][j]+matrix[i][j+1];
}
//cout << "bad robot count: " << matrix[A][B] << '\n';
if (matrix[A][B])
return -1;
int time = 0;
for (int i=0; i<=A; i++)
for (int j=0; j<=B; j++)
if ((i+j)!=(A+B))
{
int time_taken = cel(matrix[i][j], A-i+B-j);
//cout << "row i contains " << matrix[i][j] << " toys, cumulatively and it takes " << time_taken << '\n';
time = max(time, time_taken);
}
return time;
}
