#include "robots.h"
#define N 50000
#define M 50000
#define K 1000000
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *aa;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[ii[j]] == aa[i_])
j++;
else if (aa[ii[j]] < aa[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int putaway(int n, int m, int k, int xx[], int yy[], int ww[], int ss[]) {
static int ii[N], jj[M], hh[K];
int h, i, j, ans;
for (i = 0; i < n; i++)
ii[i] = i;
aa = xx, sort(ii, 0, n);
for (j = 0; j < m; j++)
jj[j] = j;
aa = yy, sort(jj, 0, m);
ans = 0;
if (m == 0) {
for (h = 0; h < k; h++)
hh[h] = h;
aa = ww, sort(hh, 0, k);
for (i = 0, h = 0; i <= n; i++) {
if (i > 0)
while (h < k && ww[hh[h]] < xx[ii[i - 1]])
h++;
if (i < n)
ans = max(ans, (k - h + n - i - 1) / (n - i));
else if (h != k)
return -1;
}
} else {
for (i = 0; i <= n; i++)
for (j = 0; j <= m; j++) {
int x = i == 0 ? 0 : xx[ii[i - 1]], y = j == 0 ? 0 : yy[jj[j - 1]], cnt;
cnt = 0;
for (h = 0; h < k; h++)
if (ww[h] >= x && ss[h] >= y)
cnt++;
if (i < n || j < m)
ans = max(ans, (cnt + n - i + m - j - 1) / (n - i + m - j));
else if (cnt != 0)
return -1;
}
}
return ans;
}
