| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1192462 | lance0 | Robots (IOI13_robots) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]) {
vector<int> x,y;
int rob_w_max = 0, rob_s_max = 0;
for (int i = 0; i < A; i++) {
x.push_back(X[i]);
rob_w_max = max(rob_w_max, X[i]);
}
for (int i = 0; i < B; i++) {
y.push_back(Y[i]);
rob_s_max = max(rob_s_max, Y[i]);
}
//note: weakest robots should take as much as possible first since size will never affect them
sort(x.begin(),x.end());
//but largest robots should take as much as possible to ensure smaller robots have something to grab
sort(y.begin(),y.end(), greater<int>());
int w_max = 0, s_max = 0;
//combine weight/size requirements into one array for sorting
vector<pair<int,int>> ws;
bool flag = true;
for (int i = 0; i < T; i++) {
if (W[i] >= x[A-1] and S[i] >= y[B-1]) {
flag = false;
break;
}
ws.push_back(make_pair(W[i],S[i]));
}
sort(ws.begin(),ws.end());
//cleaner to do it now than worry about it in binsearch, though slower
if (flag == false) {
return -1;
} else {
int low = 0, high = T;
while(low < high) {
int mid = (low + high) / 2;
priority_queue<int> pq;
int count = 0; // counting toys doable by weak
for (int i = 0; i < A; i++) {
while (count < T) {
if (ws[count].first < x[i]) {
pq.push(ws[count].second);
count++;
} else {
break;
}
}
for (int j = 0; j < mid; j++) {
if (!pq.empty()) {
pq.pop();
} else {
break;
}
}
}
for (int i = count; i < T; i++) {
pq.push(ws[i].second);
}
for (int i = 0; i < B; i++) {
if (pq.size() == 0) {
break;
} else {
for (int j = 0; j < mid; j++) {
if (!pq.empty()) {
if (pq.top() < y[i]) {
pq.pop();
}
} else {
break;
}
}
}
}
if (pq.size() > 0) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}