# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
578994 | Mazaalai | Robots (IOI13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "robots.h"
#include <bits/stdc++.h>
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define ff first
#define ss second
#define LINE "--------------------\n"
using namespace std;
using PII = pair <int, int>;
int n, m, k, a, b;
const int N = 5e4+5;
const int M = 1e6+5;
int wLimit[N], szLimit[N];
PII toys[M];
bool solve(int lim) {
priority_queue <int> vals;
// cout << LINE;
int i, j;
for (i = a-1, j = n-1; i >= 0 && j >= 0; i--) {
int removed = 0;
while(j >= 0 && removed < lim) {
if (toys[j].ff < wLimit[i]) {
removed++;
else vals.push(toys[j].ss);
j--;
}
}
while(j >= 0) vals.push(toys[j--].ss);
for (int i = b-1; i >= 0; i--) {
if (!vals.empty() && !(vals.top() < szLimit[i])) return 0;
for (int j = 0; j < lim && !vals.empty(); j++) vals.pop();
}
return vals.empty();
}
int putaway(int weak, int small, int _n, int _wLimit[], int _szLimit[], int _w[], int _sz[]) {
n = _n;
a = weak;
b = small;
for (int i = 0; i < weak; i++) wLimit[i] = _wLimit[i];
for (int i = 0; i < small; i++) szLimit[i] = _szLimit[i];
for (int i = 0; i < n; i++) toys[i] = {_w[i], _sz[i]};
if (n > 0) sort(toys, toys+n);
if (a > 0) sort(wLimit, wLimit+a);
if (b > 0) sort(szLimit, szLimit+b);
if (n == 0) return 0;
int l = 1, r = n, ans = 1e9;
// l = r = 3;
while (l <= r) {
int mid = (l+r)>>1;
if (solve(mid)) {
// cout << "A\n";
r = mid-1;
ans = mid;
} else {
// cout << "B\n";
l = mid+1;
}
}
return ans == 1e9 ? -1 : ans;
}