#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 1e6 + 7;
const int L = 1000 + 7;
int cover1[N];
int cover2[N];
vector<int> la[L];
int cnt[L][L];
int sz1;
int sz2;
ll value[L];
bool isok(int k) {
/// (i + j) * k >= cnt[i][j]
/// la un i anumit imi pasa de i * k >= cnt[i][j] - j * k
/// cnt[i][j] - j * k trebuie sa fie maxim
for (int j = 0; j <= sz2; j++) {
value[j] = -(j * (ll) k);
}
for (int i = 0; i <= sz1; i++) {
for (auto &j : la[i]) {
for (int k = j; k <= sz2; k++) {
value[k]++;
}
}
ll themax = 0;
for (int j = 0; j <= sz2; j++) {
themax = max(themax, value[j]);
}
bool ok = (i * (ll) k >= themax);
if (!ok) {
return 0;
}
}
return 1;
for (int i = 0; i <= sz1; i++) {
for (int j = (i == 0); j <= sz2; j++) {
int up = cnt[i][j];
int down = i + j;
/// down * smth >= up
if ((ll) down * k < up) {
return 0;
}
}
}
return 1;
}
int putaway(int __sz1, int __sz2, int n, int val1[], int val2[], int x[], int y[]) {
sz1 = __sz1;
sz2 = __sz2;
assert(sz1 < L);
assert(sz2 < L);
vector<pair<int, int>> xx, yy;
for (int i = 0; i < n; i++) {
xx.push_back({x[i], i});
yy.push_back({y[i], i});
cover1[i] = -1;
cover2[i] = -1;
}
sort(xx.rbegin(), xx.rend());
sort(yy.rbegin(), yy.rend());
for (int i = 0; i < sz1; i++) {
val1[i]--;
}
for (int i = 0; i < sz2; i++) {
val2[i]--;
}
sort(val1, val1 + sz1); reverse(val1, val1 + sz1);
sort(val2, val2 + sz2); reverse(val2, val2 + sz2);
{
int p1 = 0;
for (auto &it : xx) {
while (p1 < sz1 && it.first <= val1[p1]) p1++;
cover1[it.second] = p1;
}
}
{
int p2 = 0;
for (auto &it : yy) {
while (p2 < sz2 && it.first <= val2[p2]) p2++;
cover2[it.second] = p2;
}
}
for (int i = 0; i < n; i++) {
assert(0 <= cover1[i] && cover1[i] <= sz1);
assert(0 <= cover2[i] && cover2[i] <= sz2);
cnt[cover1[i]][cover2[i]]++;
la[cover1[i]].push_back(cover2[i]);
}
for (int i = 0; i <= sz1; i++) {
for (int j = 1; j <= sz2; j++) {
cnt[i][j] += cnt[i][j - 1];
}
}
for (int i = 1; i <= sz1; i++) {
for (int j = 0; j <= sz2; j++) {
cnt[i][j] += cnt[i - 1][j];
}
}
if (cnt[0][0]) {
return -1;
}
int low = 1, high = n, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (isok(mid)) {
sol = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
assert(sol != -1);
return sol;
int mx = 0;
for (int i = 0; i <= sz1; i++) {
for (int j = (i == 0); j <= sz2; j++) {
int up = cnt[i][j];
int down = i + j;
/// down * smth >= up
int smth = (up + down - 1) / down;
mx = max(mx, smth);
}
}
return mx;
for (int i = 0; i <= sz1; i++) {
for (int j = 0; j <= sz2; j++) {
cout << cnt[i][j] << " ";
}
cout << "\n";
}
exit(0);
for (int i = 0; i < n; i++) {
cout << cover1[i] << " " << cover2[i] << "\n";
}
return 42;
}
