#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int w[1000005], s[1000005];
bool cmpw(int a, int b){
if (w[a] != w[b]) return w[a] < w[b];
else return s[a] < s[b];
}
bool cmps(int a, int b){
if (s[a] != s[b]) return s[a] < s[b];
else return w[a] < w[b];
}
bool cando(int x, int A, int B, int T, int X[], int Y[], int W[], int S[]){
//printf("\t\t\t\tTesting %d\n",x);
vector<int> v(T);
for (int i = 0; i < T; i++) v[i] = i;
sort(v.begin(),v.end(),cmpw);
int curT = 0, curA = 0;
priority_queue<ii> pq;
while (curT < T && curA < A){
//printf("toy %d weight %d robot %d\n",v[curT],W[v[curT]],curA);
if (X[curA] <= W[v[curT]]){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d weight %d\n",curA,pq.top().second,pq.top().first);
pq.pop();
}
curA++;
}
else{
pq.push(ii(S[v[curT]],v[curT]));
curT++;
}
}
while (curA++ < A){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curA,pq.top().second,pq.top().first);
pq.pop();
}
}
vector<int> v2;
while(pq.size()){
v2.push_back(pq.top().second);
//printf("toy %d not taken by weight\n",pq.top().second);
pq.pop();
}
while (curT < T){
//printf("toy %d not taken by weight\n",v[curT]);
v2.push_back(v[curT++]);
}
sort(v2.begin(),v2.end(),cmps);
int curB = 0;
curT = 0;
while (curT < v2.size() && curB < B){
//printf("toy %d size %d robot %d\n",v2[curT],S[v2[curT]],curB);
if (Y[curB] <= S[v2[curT]]){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
pq.pop();
}
curB++;
}
else{
pq.push(ii(W[v2[curT]],v2[curT]));
curT++;
}
}
while (curB++ < B){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
pq.pop();
}
}
if (pq.empty() && curT == v2.size()){
//printf("none left\n");
return true;
}
else{
//printf("some left\n");
while (pq.size()){
//printf("toy %d not taken\n",pq.top().second);
pq.pop();
}
return false;
}
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for (int i = 0; i < T; i++){
w[i] = W[i];
s[i] = S[i];
}
sort(X,X+A);
sort(Y,Y+B);
int lo = 0, hi = T+1;
while (lo + 1 < hi){
//printf("%d %d\n",lo,hi);
int mid = (lo+hi)/2;
if (cando(mid,A,B,T,X,Y,W,S)){
hi = mid;
}
else lo = mid;
}
if (lo + 1 == hi){
//printf("%d %d\n",lo,hi);
if (cando(lo,A,B,T,X,Y,W,S)) hi = lo;
else lo = hi;
}
if (lo == T+1) return -1;
return lo;
}
