| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 779301 | math_rabbit_1028 | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "robots.h"
using namespace std;
int a, b, t;
struct toy {
int w, s;
bool operator< (const toy &other) const {
if (w == other.w) return s < other.s;
return w < other.w;
}
} toys[1010101];
bool compare(toy t1, toy t2) {
if (t1.s == t2.s) return t1.w > t2.w;
return t1.s > t2.s;
}
int wrbt[50505], srbt[50505];
priority_queue<toy> pq, pq2;
bool solve(int d) {
while (!pq.empty()) pq.pop();
while (!pq2.empty()) pq2.pop();
int p = 1;
long long remain = 0;
for (int i = b; i >= 0; i--) {
while (p <= t) {
if (toys[p].s >= srbt[i]) {
pq2.push(toys[p]);
p++;
}
else break;
}
while (!pq2.empty()) {
if (remain > 0) {
pq2.pop();
remain--;
}
else break;
}
while (!pq2.empty()) {
pq.push(pq2.top());
pq2.pop();
}
remain += d;
}
long long cnt = 0;
for (int i = a; i >= 0; i--) {
while (!pq.empty()) {
if (pq.top().w >= wrbt[i]) {
cnt++;
pq.pop();
}
else break;
}
if (cnt > (long long)d * (a - i)) return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a = A; b = B; t = T;
for (int i = 1; i <= a; i++) wrbt[i] = X[i];
for (int i = 1; i <= b; i++) srbt[i] = Y[i];
for (int i = 1; i <= t; i++) {
toys[i].w = W[i];
toys[i].s = S[i];
}
sort(wrbt + 1, wrbt + a + 1);
sort(srbt + 1, srbt + b + 1);
sort(toys + 1, toys + t + 1, compare);
for (int i = 1; i <= t; i++) {
if (toys[i].w >= wrbt[a] && toys[i].s >= srbt[b]) {
cout << "-1\n";
return 0;
}
}
int st = 1, ed = t;
//assert(solve(t));
while (st < ed) {
int mid = (st + ed) / 2;
if (solve(mid)) {
ed = mid;
}
else {
st = mid + 1;
}
}
cout << st << "\n";
return 0;
}