| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1187081 | harvsftw | Robots (IOI13_robots) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define F(i, n) for(int i = 0; i < (n); i++)
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
using state = tuple<int, int, int>;
sort(X, X + A);
sort(Y, Y + B);
vector<state> by_weight;
F(i, T) {
by_weight.emplace(W[i], S[i], i);
}
sort(by_weight.begin(), by_weight.end());
auto solver = [&](int num_per_robot) {
priority_queue<pair<int, int>> pq;
auto it = by_weight.begin();
F(i, A) {
int robot_weight_limit = X[i];
while(it != by_weight.end() && get<0>(*it) < robot_weight_limit) {
pq.emplace(get<1>(*it), get<2>(*it));
++it;
}
int cnt = num_per_robot;
while(!pq.empty() && cnt > 0) {
pq.pop();
cnt--;
}
}
priority_queue<int> by_size;
while(!pq.empty()) {
pq.pop();
by_size.emplace(-S[idx]);
}
while(it != by_weight.end()) {
by_size.emplace(-get<1>(*it));
++it;
}
F(i, B) {
int robot_size_limit = Y[i];
int cnt = num_per_robot;
while(by_size.size() && -by_size.top() < robot_size_limit && cnt > 0) {
by_size.pop();
cnt--;
}
}
return by_size.empty();
};
int l = 1, r = T;
while(l <= r) {
int m = (l + r) / 2;
if(solver(m)) {
r = m - 1;
} else {
l = m + 1;
}
}
if(!solver(l)) {
return -1;
}
return l;
};