#include <bits/stdc++.h>
#include "robots.h"
#define fail(s, x...) do {fprintf(stderr, s "\n", ## x);exit(1);}while(0)
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define lb lower_bound
#define mod 1000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n, m, k, x[N], y[N], kalx[N], kaly[N];
ii a[N];
set < ii > :: iterator it, it2;
bool dene(int kal){
if(kal*(m + k) < n)
return 0;
set < ii > xx, yy;
priority_queue < int > s;
for(int i = 1; i <= m; i++){
kalx[i] = kal;
xx.insert(mp(x[i], i));
}
for(int i = 1; i <= k; i++){
kaly[i] = kal;
yy.insert(mp(y[i], i));
}
for(int i = 1; i <= n; i++){
// cout << xx.size() << " " << yy.size() << " " << s.size() << endl;
it = xx.lb(mp(a[i].st, 0));
if(it == xx.end()){
it2 = yy.lb(mp(a[i].nd, 0));
if(it2 != yy.end()){
kaly[it2->nd]--;
if(kaly[it2->nd] == 0)
yy.erase(it2);
// cout << "ikinciye doldurduk " << it2->st << " " << it2->nd << " " << kaly[it2->nd] << endl;
continue;
}
if(s.empty())
return 0;
int amk = -s.top();
s.pop();
it2 = yy.lb(mp(amk, 0));
if(it2 == yy.end())
return 0;
kaly[it2->nd]--;
if(kaly[it2->nd] == 0)
yy.erase(it2);
s.push(-a[i].nd);
continue;
}
kalx[it->nd]--;
if(kalx[it->nd] == 0)
xx.erase(it);
s.push(-a[i].nd);
// cout << "birinciye doldurduk " << it->st << " " << it->nd << " " << kalx[it->nd] << endl;
}
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n = T;m = A;k = B;
for(int i = 0; i < m; i++)
x[i + 1] = X[i];
sort(x + 1, x + m + 1);
for(int i = 0; i < k; i++)
y[i + 1] = Y[i];
sort(y + 1, y + k + 1);
for(int i = 0; i < n; i++){
a[i + 1] = mp(W[i] + 1, S[i] + 1);
if(W[i] + 1 > x[m] and S[i] + 1 > y[k])
return -1;
}
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
// for(int i = 1; i <= n; i++)cout << a[i].st << " ";cout << endl;
// for(int i = 1; i <= n; i++)cout << a[i].nd << " ";cout << endl;
// dene(2);
int bas = 1, son = n;
while(bas < son){
if(dene(orta))
son = orta;
else
bas = orta + 1;
}
return orta;
}
// #define MAX_A 50000
// #define MAX_B 50000
// #define MAX_T 500000
// static int X[MAX_A];
// static int Y[MAX_B];
// static int W[MAX_T];
// static int S[MAX_T];
// int main() {
// freopen("out.txt", "w", stdout);
// int A, B, T, i;
// int res;
// FILE *f = fopen("in.txt", "r");
// if (!f)
// fail("Failed to open input file.");
// res = fscanf(f, "%d", &A);
// if (res != 1)
// fail("Failed to read A from input file.");
// if (A < 0 || A > MAX_A)
// fail("A is out of bounds.");
// res = fscanf(f, "%d", &B);
// if (res != 1)
// fail("Failed to read B from input file.");
// if (B < 0 || B > MAX_B)
// fail("B is out of bounds.");
// res = fscanf(f, "%d", &T);
// if (res != 1)
// fail("Failed to read T from input file.");
// if (T < 1 || T > MAX_T)
// fail("T is out of bounds.");
// for (i = 0; i < A; i++) {
// res = fscanf(f, "%d", &X[i]);
// if (res != 1)
// fail("Failed to read data from input file.");
// }
// for (i = 0; i < B; i++) {
// res = fscanf(f, "%d", &Y[i]);
// if (res != 1)
// fail("Failed to read data from input file.");
// }
// for (i = 0; i < T; i++) {
// res = fscanf(f, "%d%d", &W[i], &S[i]);
// if (res != 2)
// fail("Failed to read data from input file.");
// }
// fclose(f);
// int answer = putaway(A, B, T, X, Y, W, S);
// printf("%d\n", answer);
// return 0;
// }
