| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314787 | kawhiet | 로봇 (IOI13_robots) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int putaway(int n, int m, int t, int _x[], int _y[], int _w[], int _s[]) {
vector<int> x(n), y(m), w(t), s(t);
for (int i = 0; i < n; i++) {
x[i] = _x[i];
}
for (int i = 0; i < m; i++) {
y[i] = _y[i];
}
vector<int> ord(t);
ranges::iota(ord, 0);
ranges::sort(ord, [&](int i, int j) {
return _w[i] < _w[j];
});
for (int i = 0; i < t; i++) {
w[i] = _w[ord[i]];
s[i] = _s[ord[i]];
}
for (int i = 0; i < t; i++) {
if (w[i] >= x[n - 1] && s[i] >= y[m - 1]) {
return -1;
}
}
ranges::sort(x);
ranges::sort(y);
auto good = [&](int k) {
int pos = 0;
vector<bool> removed(t);
for (int i = 0; i < n; i++) {
int l = pos;
while (pos < t && w[pos] < x[i]) {
pos++;
}
if (pos == n) break;
priority_queue<pair<int, int>> q;
for (int j = l; j < pos; j++) {
q.push({s[j], j});
}
for (int j = 0; j < k; j++) {
if (q.empty()) break;
int r = q.top().second;
q.pop();
removed[r] = 1;
}
}
vector<int> a;
for (int i = 0; i < t; i++) {
if (!removed[i]) {
a.push_back(s[i]);
}
}
ranges::sort(a);
int sz = a.size();
if (m * k < sz) {
return false;
}
vector<int> b(sz);
int ptr = m - 1;
for (int j = sz - 1; j >= 0; j -= k) {
for (int i = sz - 1; i >= max(0, j - k); i--) {
b[i] = y[ptr];
}
ptr--;
if (ptr == -1) {
break;
}
}
for (int i = 0; i < sz; i++) {
if (a[i] >= b[i]) {
return false;
}
}
return true;
};
int tl = 0, tr = t;
while (tl + 1 < tr) {
int tm = (tl + tr) / 2;
if (good(tm)) {
tr = tm;
} else {
tl = tm;
}
}
return tr;
}