#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
struct Toy{
int weight;
int size;
bool operator < (Toy const &a) const{
return weight < a.weight;
}
};
int const nmax = 1000000;
Toy v[1 + nmax];
int weak[1 + nmax], small[1 + nmax];
int N, M, T;
bool test(int time){
int ptr = 0;
std::priority_queue<int> pq;
for(int i = 0; i < N; i++) {
while(ptr < T && v[ptr].weight < weak[i])
pq.push(v[ptr++].size);
for(int h = 0;h < time; h++)
if(0 < pq.size())
pq.pop();
else
break;
}
while(ptr < T)
pq.push(v[ptr++].size);
for(int i = M - 1;0 <= i; i--){
for(int h = 0; h < time; h++)
if(0 < pq.size() && pq.top() < small[i])
pq.pop();
else
break;
}
return 0 == pq.size();
}
int binarysearch(int from, int to){
if(from < to){
int mid = (from + to) / 2;
if(test(mid) == 1)
return binarysearch(from, mid);
else
return binarysearch(mid + 1, to);
} else
return from;
}
int putaway(int N_, int M_, int T_, int X[], int Y[], int W[], int S[]) {
N = N_;
M = M_;
T = T_;
std::sort(X, X + N);
std::sort(Y, Y + M);
for(int i = 0; i < N; i++)
weak[i] = X[i];
for(int i = 0; i < M; i++)
small[i] = Y[i];
for(int i = 0; i < T; i++) {
v[i].weight = W[i];
v[i].size = S[i];
}
std::sort(v, v + T);
//*
int result = binarysearch(1, T + 1);
if(result == T + 1)
return -1;
else
return result;
//*/
}
