#include <bits/stdc++.h>
#include "robots.h"
#define DIM 1000010
using namespace std;
pair <int,int> v[DIM];
set <pair<int,int> > s,s2;
int a[DIM],b[DIM];
int try_robot_size (int val){
set <pair<int,int> > :: iterator it = s2.lower_bound(make_pair(val,0));
if (it == s2.end() || it->first < val)
return 0;
int nr = it->first, cnt = it->second;
s2.erase(make_pair(nr,cnt));
cnt--;
if (cnt)
s2.insert(make_pair(nr,cnt));
return 1;
}
int try_robot_weight (int val){
set <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(make_pair(nr,cnt));
cnt--;
if (cnt)
s.insert(make_pair(nr,cnt));
return 1;
}
int verif (int val, int n){
int i;
s.clear(), s2.clear();
for (i=1;i<=a[0];i++)
s.insert(make_pair(a[i],val));
for (i=1;i<=b[0];i++)
s2.insert(make_pair(b[i],val));
for (i=n;i;i--){
/// incerc sa cuplez jucaria asta cu un robot de marime
int ok = try_robot_size(v[i].second);
if (!ok)
ok |= try_robot_weight(v[i].first);
if (!ok)
return 0;
}
return 1;
}
int putaway (int nr, int nr2, int n, int A[], int B[], int Weight[], int Size[]){
int i;
for (i=0;i<n;i++)
v[i+1] = make_pair(Weight[i],Size[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);
}
for (i=1;i<=n;i++){
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;
}
