| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 815951 | makanhulia | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 2e5 + 5;
set<pair<int, int>> sA, sB, s1, s2;
priority_queue<pair<int, int>> pq;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X + A);
sort(Y, Y + B);
for (int i = 0; i < T; i++) if (W[i] >= X[A - 1] and S[i] >= Y[B - 1]) return -1;
for (int i = 0; i < T; i++) sA.insert({W[i], i});
for (int i = 0; i < T; i++) sB.insert({S[i], i});
int l = (T - 1) / (A + B) + 1, r = T;
while (l < r) {
int m = (l + r) / 2, id1 = 0, id2 = 0;
s1 = sA, s2 = sB;
while (!pq.empty()) pq.pop();
for (auto i : s1) {
while (id1 < A and X[id1] <= i.fi) {
for (int j = 0; j < m and !pq.empty(); j++) {
int idx = pq.top().se;
s1.erase({W[idx], idx});
s2.erase({S[idx], idx});
pq.pop();
}
id1++;
}
if (id1 == A) break;
pq.push({S[i.se], i.se});
}
while (id1 < A) {
for (int j = 0; j < m and !pq.empty(); j++) {
int idx = pq.top().se;
s1.erase({W[idx], idx});
s2.erase({S[idx], idx});
pq.pop();
}
id1++;
}
while (!pq.empty()) pq.pop();
for (auto i : s2) {
while (id2 < B and Y[id2] <= i.fi) {
for (int j = 0; j < m and !pq.empty(); j++) {
int idx = pq.top().se;
s1.erase({W[idx], idx});
s2.erase({S[idx], idx});
pq.pop();
}
id2++;
}
if (id2 == B) break;
pq.push({W[i.se], i.se});
}
while (id2 < B) {
for (int j = 0; j < m and !pq.empty(); j++) {
int idx = pq.top().se;
s1.erase({W[idx], idx});
s2.erase({S[idx], idx});
pq.pop();
}
id2++;
}
if (s1.empty()) r = m;
else l = m + 1;
// for (auto x : s1) cout << x.fi << " " << x.se << "qihdf\n";
// for (auto x : s2) cout << x.fi << " " << x.se << "pfawl\n";
// cout << m << " " << s1.size() << " " << s2.size() << "fwao\n";
}
return l;
}
#define fail(s, x...) do { fprintf(stderr, s "\n", ## x); exit(1); } while(0)
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 1000000
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;
int res;
FILE *f = fopen("robots.txt", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d", &A);
if (res != 1)
fail("Failed to read A from input file.");
if (A < 0 || A > MAX_A)
fail("A is out of bounds.");
res = fscanf(f, "%d", &B);
if (res != 1)
fail("Failed to read B from input file.");
if (B < 0 || B > MAX_B)
fail("B is out of bounds.");
res = fscanf(f, "%d", &T);
if (res != 1)
fail("Failed to read T from input file.");
if (T < 1 || T > MAX_T)
fail("T is out of bounds.");
for (i = 0; i < A; i++) {
res = fscanf(f, "%d", &X[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < B; i++) {
res = fscanf(f, "%d", &Y[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < T; i++) {
res = fscanf(f, "%d%d", &W[i], &S[i]);
if (res != 2)
fail("Failed to read data from input file.");
}
fclose(f);
int answer = putaway(A, B, T, X, Y, W, S);
printf("%d\n", answer);
return 0;
}