#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> toys;
bool check(int a, int b, int t, int x[], int y[], int k){
if(k > t) return true;
vector<int> cnt(a + 1, 0);
set<pair<int, int>> robots;
for(int i=0; i<a; i++) robots.insert({x[i] - 1, i});
int l_b = b - 1, cnt_b = 0;
for(int i=0; i<t; i++){
auto [s, w] = toys[i];
auto pos = robots.lower_bound({w, 0});
if(pos == robots.end()){
if(l_b < 0 || y[l_b] <= s) return false;
cnt_b ++;
if(cnt_b == k) l_b --, cnt_b = 0;
continue;
}
cnt[pos->second] ++;
if(cnt[pos->second] == k) robots.erase(*pos);
}
return true;
}
int bs(int a, int b, int t, int x[], int y[]){
int l = 1, r = t + 1;
while(l < r){
int m = l + (r - l) / 2;
if(check(a, b, t, x, y, m)) r = m;
else l = m + 1;
}
return r;
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]){
toys.clear();
for(int i=0; i<t; i++) toys.push_back({s[i], w[i]});
sort(toys.rbegin(), toys.rend());
sort(x, x + a);
sort(y, y + b);
int ans = bs(a, b, t, x, y);
return (ans > t ? -1 : ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |