이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 50010
vector<int> sizes[maxn];
vector<int> ys;
int a, b;
bool check(int mid) {
multiset<int> active;
for (int i = 0; i < a; i++) {
for (int vv : sizes[i]) active.insert(vv);
for (int j = 0; j < mid; j++) {
if (!active.size()) break;
auto it = active.end();
--it;
active.erase(it);
}
}
for (int vv : sizes[a]) active.insert(vv);
// // cout << mid << " interim size: " << active.size() << endl;
// for (int thing : active) {
// cout << " " << thing << endl;
// }
for (int cur : ys) {
//go in order, starting with cur
// cout << " ---- cur: " << cur << endl;
if (!active.size()) break;
for (int j = 0; j < mid; j++) {
if (!active.size()) break;
auto it = active.lower_bound(cur);
if (it == active.begin()) break;
--it;
active.erase(it);
}
}
return active.size() == 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int lo = 1, hi = T;
//X is weight limits for A type robots
//Y is size limits for B type robogts
//limits cannot be equal
a = A;
b = B;
sort(X, X+A);
sort(Y, Y+B);
// cout << "Array of A" << endl;
// cout << " ";
// for (int i = 0; i < A; i++) cout << X[i] << " ";
// cout << endl;
for (int i = 0; i < B; i++) ys.push_back(Y[i]);
for (int i = 0; i < T; i++) {
if ((A == 0 || W[i] >= X[A-1]) &&
(B == 0 || S[i] >= Y[B-1])) {
return -1;
}
//push back to largest A
int cw = W[i];
int cs = S[i];
int cl = 0;
int ch = A-1;
//manually doing the binary search thing
//find first guy this works for
if (A == 0 || cw >= X[A-1]) {
// cout <<"--> " << cw << " " << cs << " " << A << endl;
sizes[A].push_back(cs);
}
else {
while (cl < ch) {
int mid = (cl+ch)/2;
if (X[mid] > cw) {
//this spot works
ch = mid;
}
else cl = mid+1; //does not work for this value
}
// cout << "--> " << cw << " " << cs << " " << cl << endl;
sizes[cl].push_back(cs);
}
}
while (lo < hi) {
int mid = (lo+hi)/2;
if (check(mid)) {
// cout << "something worked" << endl;
hi = mid;
}
else lo = mid+1;
}
return lo;
}
# | 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... |