| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1116067 | crafticat | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define F0R(i, n) for (ll i = 0; i < n;i++)
#define FOR(i,j, n) for (ll i = j; i < n;i++)
template<typename T>
using V = vector<T>;
using vi = V<ll>;
using vb = V<bool>;
using pi = pair<ll, ll>;
#define f first
#define s second
#define all(x) begin(x), end(x)
constexpr ll INF = 1e11;
V<pi> scan(V<pi> arr, vi xL, ll k) {
sort(all(arr));
reverse(all(arr));
multiset<pi> elms;
for (auto x : xL) {
elms.emplace(x, k);
}
V<pi> results;
for (auto [a,b] : arr) {
auto it = elms.upper_bound({b, INF});
if (it == elms.end()) {
results.emplace_back(a,b);
continue;
}
auto [x, am] = *it;
elms.erase(it); am--;
if (am > 0) elms.emplace(x, am);
}
return results;
}
bool ok(vi x, vi y, V<pi> elms, ll k) {
for (auto &[a,b] : elms) swap(a,b );
elms = scan(elms, x, k);
for (auto &[a,b] : elms) swap(a,b );
elms = scan(elms, y, k);
return elms.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
ll l = 0, r = INF;
vi x(A), y(B);
V<pi> elms(T);
F0R(i, A) {
x[i] = X[i];
}
F0R(i, B) {
y[i] = Y[i];
}
F0R(i, T) {
elms[i] = {W[i], S[i]};
}
while (r > l) {
ll mid = l + (r - l) / 2;
if (!ok(x, y, elms, mid)) {
l = mid + 1;
} else {
r = mid;
}
}
if (l >= INF) return -1;
return l;
}
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000
static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];
int main() {
int A, B, T, i;
assert(scanf("%d", &A) == 1);
assert(scanf("%d", &B) == 1);
assert(scanf("%d", &T) == 1);
for (i = 0; i < A; i++)
assert(scanf("%d", &X[i]) == 1);
for (i = 0; i < B; i++)
assert(scanf("%d", &Y[i]) == 1);
for (i = 0; i < T; i++)
assert(scanf("%d%d", &W[i], &S[i]) == 2);
int answer = putaway(A, B, T, X, Y, W, S);
printf("%d\n", answer);
return 0;
}