#include "robots.h" #include <bits/stdc++.h> using namespace std; #define pb push_back using pr = pair<int, int>; const int INF = 1e9+7, MOD = 1e9+7; int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { // return 9; sort(X, X + A); sort(Y, Y + B); vector<array<int, 3>> toy(T), tox(T); for (int i = 0; i < T; i++) { toy[i] = {W[i], S[i], i}; tox[i] = {W[i], S[i], i}; bool can = false; for (int j = 0; j < A && !can; j++) if (X[j] > W[i]) can = true; for (int j = 0; j < B && !can; j++) if (Y[j] > S[i]) can = true; if (!can) return -1; } sort(toy.begin(), toy.end()); sort(tox.begin(), tox.end(), [](const array<int, 3>& x, const array<int, 3>& y) { return x[1] < y[1]; }); vector<int> where(T); for (int i = 0; i < T; i++) { where[tox[i][2]] = i; } int l = 0, r = T+1; while (l < r) { int m = (l + r) >> 1; bool good = 0; priority_queue<pr> sz; vector<bool> used(T, 0); for (int i = 0, j = 0; i < A; i++) { while (j < T && X[i] > toy[j][0]) { sz.push({toy[j][1], j}); j++; } for (int k = 0; k < m; k++) { if (sz.empty()) break; auto [s, p] = sz.top(); sz.pop(); used[p] = 1; } } vector<int> unused; for (int i = 0; i < T; i++) { if (!used[i]) unused.pb(tox[where[toy[i][2]]][1]); } //sort(unused.begin(), unused.end()); for (int i = 0, j = 0; i < B; i++) { for (int k = 0; k < m; k++) { if (j < unused.size() && unused[j] < Y[i]) { j++; } else break; } if (j == unused.size()) { good = 1; break; } } if (unused.empty()) good = 1; if (good) r = m; else l = m+1; } if (l == T+1) return -1; else return l; }