#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct Toy {
int w, s;
};
bool compareToys(const Toy& a, const Toy& b) {
return a.w < b.w;
}
bool check(int M, int A, int B, int T, int X[], int Y[], vector<Toy>& toys) {
priority_queue<int> pq;
int j = 0;
// Kuchsiz robotlar o'z ishini qiladi
for (int i = 0; i < A; i++) {
// Robot X[i] ko'tara oladigan barcha o'yinchoqlarni navbatga qo'shamiz
while (j < T && toys[j].w < X[i]) {
pq.push(toys[j].s);
j++;
}
// Robot M ta o'yinchoqni olib ketadi (eng katta o'lchamli o'yinchoqlarni)
int count = M;
while (count > 0 && !pq.empty()) {
pq.pop();
count--;
}
}
// Qolgan o'yinchoqlarni navbatga qo'shamiz
while (j < T) {
pq.push(toys[j].s);
j++;
}
// Kichik robotlar qolgan o'yinchoqlarni oladi
for (int i = B - 1; i >= 0; i--) {
int count = M;
while (count > 0 && !pq.empty()) {
if (pq.top() < Y[i]) {
pq.pop();
count--;
} else {
// Agar eng katta o'lchamli o'yinchoqni bu robot ololmasa,
// demak kichikroq robotlar ham ololmaydi
break;
}
}
}
return pq.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
// Robotlarni saralash
sort(X, X + A);
sort(Y, Y + B);
vector<Toy> toys(T);
for (int i = 0; i < T; i++) {
toys[i] = {W[i], S[i]};
}
sort(toys.begin(), toys.end(), compareToys);
// Imkonsizlikni tekshirish
for (int i = 0; i < T; i++) {
bool can_be_picked = false;
if (A > 0 && toys[i].w < X[A - 1]) can_be_picked = true;
if (B > 0 && toys[i].s < Y[B - 1]) can_be_picked = true;
if (!can_be_picked) return -1;
}
// Binary Search
int low = 1, high = T, ans = T;
while (low <= high) {
int mid = low + (high - low) / 2;
if (check(mid, A, B, T, X, Y, toys)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
