| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 211694 | spdskatr | 로봇 (IOI13_robots) | C++14 | 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 <vector>
#include <algorithm>
#include <utility>
#include <cstring>
#include <queue>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
int A, B, T, x[50005], y[50005], w[1000005], s[1000005], maxsz, maxwt;
pii byweight[1000005];
priority_queue<pii> pq;
int check(int time) {
// Let weak toys go first
int ptr = 0;
for (int i = 0; i < A; i++) {
while (ptr < T && byweight[ptr].fi < x[i]) {
pq.push({ s[byweight[ptr].se], byweight[ptr].se });
ptr++;
}
for (int j = 0; !pq.empty() && j < time; j++) {
pq.pop();
}
}
while (ptr < T) {
pq.push({ s[byweight[ptr].se], byweight[ptr].se });
ptr++;
}
for (int i = B-1; i >= 0; i--) {
if (!pq.empty() && pq.top().fi >= y[i]) return 0; // Game over
for (int j = 0; !pq.empty() && j < time; j++) {
pq.pop();
}
}
if (!pq.empty()) {
while (!pq.empty()) pq.pop();
return 0;
} else {
return 1;
}
}
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
A = a, B = b, T = t;
int cooked = 0;
for (int i = 0; i < A; i++) {
x[i] = X[i];
maxwt = max(maxwt, x[i]);
}
for (int i = 0; i < B; i++) {
y[i] = Y[i];
maxsz = max(maxsz, y[i]);
}
for (int i = 0; i < T; i++) {
w[i] = W[i], s[i] = S[i];
bysize[i] = { s[i], i };
byweight[i] = { w[i], i };
if (s[i] >= maxsz && w[i] >= maxwt) return -1;
}
sort(x, x+A);
sort(y, y+B);
sort(bysize, bysize+T);
sort(byweight, byweight+T);
int lo = 0, hi = 100000;
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid;
}
return hi;
}