#include <bits/stdc++.h>
#include "robots.h"
#define DIM 1000010
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
pair <int,int> v[DIM];
multiset <pair<int,int> > s;
int a[DIM],b[DIM],f[DIM];
int try_robot_size (int val){
multiset <pair<int,int> > :: iterator it = s.lower_bound(make_pair(val,0));
if (it == s.end() || it->first < val)
return 0;
int nr = it->first, cnt = it->second;
s.erase(it);
cnt--;
if (cnt)
s.insert(make_pair(nr,cnt));
return 1;
}
int verif (int val, int n){
int i;
for (i=1;i<=a[0];++i)
f[i] = 0;
s.clear();
for (i=1;i<=b[0];++i)
s.insert(make_pair(b[i],val));
int k = a[0];
for (i=n;i;--i){
/// incerc sa cuplez jucaria asta cu un robot de marime
if (s.empty() || s.rbegin()->first < v[i].second){
int nr = v[i].first;
if (k <= 0 || a[k] < nr)
return 0;
f[k]++;
if (f[k] == val)
k--;
} else try_robot_size(v[i].second);
}
return 1;
}
int putaway (int nr, int nr2, int n, int A[], int B[], int Weight[], int Size[]){
int i;
int max_weight = 0, max_size = 0;
a[0] = nr;
for (i=0;i<nr;++i){
a[i+1] = A[i] - 1;
max_weight = max (max_weight,A[i]-1);
}
b[0] = nr2;
for (i=0;i<nr2;++i){
b[i+1] = B[i] - 1;
max_size = max (max_size,B[i]-1);
}
sort (a+1,a+nr+1);
for (i=1;i<=n;++i){
v[i] = make_pair (Weight[i-1],Size[i-1]);
if (v[i].first > max_weight && v[i].second > max_size)
return -1;
}
sort (v+1,v+n+1);
int st = 1, dr = n, sol = n;
while (st <= dr){
int mid = (st+dr)>>1;
if (verif(mid,n)){
sol = mid;
dr = mid-1;
} else st = mid+1;
}
return sol;
}
