이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, R, C;
struct xy { int x, y; }a[313];
struct line { int x, ys, ye, pls; };
bool sort_x(line a, line b) { if (a.x != b.x)return a.x < b.x; return a.pls < b.pls; }
int y[121212], val[121212];
bool simulate(int l, int r, int u, int d) {
int i, j, k, yn = 0;
vector<line>L;
for (i = 0; i < n; i++) {
L.push_back({ a[i].x - l, a[i].y - u, a[i].y + d, 1 });
L.push_back({ a[i].x + r + 1, a[i].y - u,a[i].y + d,-1 });
y[yn++] = a[i].y - u; y[yn++] = a[i].y + d;
y[yn++] = a[i].y - u - 1; y[yn++] = a[i].y + d + 1;
}
L.push_back({ 1, 1, 1, 0 });
y[yn++] = 1; y[yn++] = R;
sort(y, y + yn);
yn = unique(y, y + yn) - y;
for (i = 0; i < L.size(); i++) {
if (L[i].ys < 1)L[i].ys = 1;
if (R < L[i].ye)L[i].ye = R;
L[i].ys = lower_bound(y, y + yn, L[i].ys) - y;
L[i].ye = lower_bound(y, y + yn, L[i].ye) - y;
}
sort(L.begin(), L.end(), sort_x);
int s = lower_bound(y, y + yn, 1) - y;
int e = lower_bound(y, y + yn, R) - y;
for (i = s; i <= e; i++)val[i] = 0;
for (i = 0; i < L.size();) {
if (L[i].x > C)return true;
for (j = i; j < L.size() && L[i].x == L[j].x; j++) {
for (k = L[j].ys; k <= L[j].ye; k++) {
val[k] += L[j].pls;
}
}
if (L[i].x >= 1) {
for (k = s; k <= e; k++) {
if (val[k] == 0)return false;
}
}
i = j;
}
return true;
}
int determine_d(int l, int r, int u) {
int s = 0, e = R, ret = -1;
while (s <= e) {
int m = (s + e) / 2;
if (simulate(l, r, u, m)) {
ret = m;
e = m - 1;
}
else {
s = m + 1;
}
}
return ret;
}
int determine_ud(int l, int r) {
int s = 0, e = R, ret = -1;
while (e - s >= 3) {
int p1 = (s * 2 + e) / 3, p2 = (s + e * 2) / 3;
int k1 = determine_d(l, r, p1);
int k2 = determine_d(l, r, p2);
if (k2 < 0) { s = p2 + 1; continue; }
if (k1 < 0) { s = p1 + 1; continue; }
if (p1 + k1 < p2 + k2) e = p2;
else s = p1;
}
for (int u = s; u <= e; u++) {
int d = determine_d(l, r, u);
if (d == -1)continue;
if (ret == -1 || ret > u + d) {
ret = u + d;
}
}
return ret;
}
int determine_rud(int l) {
int s = 0, e = C, ret = -1;
while (e - s >= 3) {
int p1 = (s * 2 + e) / 3, p2 = (s + e * 2) / 3;
int k1 = determine_ud(l, p1);
int k2 = determine_ud(l, p2);
if (k2 < 0) { s = p2 + 1; continue; }
if (k1 < 0) { s = p1 + 1; continue; }
if (p1 + k1 < p2 + k2) e = p2;
else s = p1;
}
for (int r = s; r <= e; r++) {
int ud = determine_ud(l, r);
if (ud == -1)continue;
if (ret == -1 || ret > r + ud) {
ret = r + ud;
}
}
return ret;
}
int main() {
int i, j, k; scanf("%d%d%d", &C, &R, &n);
for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
int l, r, u, d;
int ans = 1e9;
for (l = 0; l <= 40; l++) {
int rud = determine_rud(l);
if (rud >=0) {
ans = min(ans, l+ rud);
}
}
printf("%d", ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
cultivation.cpp: In function 'bool simulate(int, int, int, int)':
cultivation.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < L.size(); i++) {
~~^~~~~~~~~~
cultivation.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < L.size();) {
~~^~~~~~~~~~
cultivation.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = i; j < L.size() && L[i].x == L[j].x; j++) {
~~^~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:109:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k; scanf("%d%d%d", &C, &R, &n);
^
cultivation.cpp:109:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k; scanf("%d%d%d", &C, &R, &n);
^
cultivation.cpp:111:9: warning: unused variable 'r' [-Wunused-variable]
int l, r, u, d;
^
cultivation.cpp:111:12: warning: unused variable 'u' [-Wunused-variable]
int l, r, u, d;
^
cultivation.cpp:111:15: warning: unused variable 'd' [-Wunused-variable]
int l, r, u, d;
^
cultivation.cpp:109:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int i, j, k; scanf("%d%d%d", &C, &R, &n);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:110:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |