| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 639240 | classic | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
sort(x, x + a);
sort(y, y + b);
vector<pair<int, int>> c;
for (int i = 0; i < t; i++) {
c.emplace_back(w[i], s[i]);
}
sort(c.begin(), c.end());
int low = 1, hig = t;
int res = -1;
while (low <= hig) {
int mid = (low + hig) >> 1;
priority_queue<int> pq;
int idx = 0;
for (int i = 0; i < a; i++) {
while (idx < t && c[idx].first < x[i]) {
pq.emplace(c[idx].second);
idx += 1;
}
int cnt = 0;
while (!pq.empty() && cnt < mid) {
pq.pop();
cnt += 1;
}
}
while (idx < t) {
pq.emplace(c[idx].second);
idx += 1;
}
bool ok = true;
for (int i = b - 1; i >= 0; i--) {
int cnt = 0;
while (!pq.empty() && cnt < mid) {
if (pq.top() >= y[i]) {
ok = false;
}
pq.pop();
cnt += 1;
}
}
ok &= pq.empty();
if (ok) {
res = mid;
hig = mid - 1;
} else {
low = mid + 1;
}
}
return res;
}
const int N = 1e6 + 1;
int x_[N], y_[N], w_[N], s_[N];
int main() {
freopen("robots.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, t;
cin >> a >> b >> t;
for (int i = 0; i < a; i++) {
cin >> x_[i];
}
for (int i = 0; i < b; i++) {
cin >> y_[i];
}
for (int i = 0; i < t; i++) {
cin >> w_[i] >> s_[i];
}
cout << putaway(a, b, t, x_, y_, w_, s_);
return 0;
}