제출 #493520

#제출 시각아이디문제언어결과실행 시간메모리
493520rainboyIzvanzemaljci (COI21_izvanzemaljci)C11
100 / 100
307 ms11312 KiB
#include <stdio.h> #include <string.h> #include <sys/time.h> #define N 100000 #define INF 0x3f3f3f3f3f3f3f3fLL #define X 1000000001 long long min(long long a, long long b) { return a < b ? a : b; } long long max(long long a, long long b) { return a > b ? a : b; } unsigned int Z = 12345; int rand_() { return (Z *= 3) >> 1; } int xx[N], yy[N], n; int *zz; void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (zz[ii[j]] == zz[i_]) j++; else if (zz[ii[j]] < zz[i_]) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } void solve1(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) { int i, i_, x, y, xl, xr, yl, yr, s; if (n == 0) { if (ss_[0] > 1) xx_[0] = X + 1, yy_[0] = X + 1, ss_[0] = 1; return; } xl = X, xr = -X, yl = X, yr = -X; for (i = 0; i < n; i++) { i_ = ii[i], x = xx[i_], y = yy[i_]; xl = min(xl, x), xr = max(xr, x); yl = min(yl, y), yr = max(yr, y); } s = max(max(xr - xl, yr - yl), 1); if (ss_[0] > s) xx_[0] = xl, yy_[0] = yl, ss_[0] = s; } void solve2(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) { static int ypl[N], ypr[N], yql[N], yqr[N]; int i, xl, xr, xp, xq, y, yl, yr, s; long long x0, y0, s0, x1, y1, s1; if (n == 0) { if (max(ss_[0], ss_[1]) > 1) { xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1; xx_[1] = X + 1, yy_[1] = -(X + 2), ss_[1] = 1; } return; } xl = xx[ii[0]], xr = xx[ii[n - 1]]; yl = X, yr = -X; for (i = 0; i < n; i++) { y = yy[ii[i]]; ypl[i] = yl = min(yl, y); ypr[i] = yr = max(yr, y); } yl = X, yr = -X; for (i = n - 1; i >= 0; i--) { y = yy[ii[i]]; yql[i] = yl = min(yl, y); yqr[i] = yr = max(yr, y); } for (i = -1; i < n; i++) { xp = i == -1 ? -(X + 1) : xx[ii[i]], xq = i + 1 == n ? X + 1 : xx[ii[i + 1]]; if (xp == xq) continue; if (i == -1) s0 = 1, x0 = -(X + 2), y0 = -(X + 2); else s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1), x0 = xp - s0, y0 = ypr[i] - s0; if (i + 1 == n) s1 = 1, x1 = X + 1, y1 = -(X + 2); else s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1), x1 = xq, y1 = yqr[i + 1] - s1; s = max(s0, s1); if (max(ss_[0], ss_[1]) > s) { xx_[0] = x0, yy_[0] = y0, ss_[0] = s0; xx_[1] = x1, yy_[1] = y1, ss_[1] = s1; } } } void solve21(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) { static long long xx1[3], yy1[3], ss1[3]; static int ii1[N], ii2[N]; int n1, n2, h, i, i_, lower, upper; lower = -X, upper = X; while (upper - lower > 1) { int y = (lower + upper) / 2; n1 = n2 = 0; for (i = 0; i < n; i++) { i_ = ii[i]; if (yy[i_] <= y) ii1[n1++] = i_; else ii2[n2++] = i_; } ss1[0] = ss1[1] = ss1[2] = INF; solve2(ii1, n1, xx1, yy1, ss1), solve1(ii2, n2, xx1 + 2, yy1 + 2, ss1 + 2); if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(ss1[0], ss1[1]), ss1[2])) for (h = 0; h < 3; h++) xx_[h] = xx1[h], yy_[h] = yy1[h], ss_[h] = ss1[h]; if (max(ss1[0], ss1[1]) < ss1[2]) lower = y; else upper = y; } } int ypl[N], ypr[N], yql[N], yqr[N], ysl[N], ysr[N], ytl[N], ytr[N], xl, xr, xp, xq, xs, xt, yl, yr; long long x0, y0, s0, x1, y1, s1, x2, y2, s2; void try(int *ii, int n, int i, int j, long long *xx_, long long *yy_, long long *ss_) { xp = i == 0 ? -(X + 1) : xx[ii[i - 1]], xs = xx[ii[i]]; xt = xx[ii[j]], xq = j + 1 == n ? X + 1 : xx[ii[j + 1]]; yl = min(ysl[i], ytl[j]), yr = max(ysr[i], ytr[j]); if (xp < xs && xt < xq && (i == 0 || j + 1 == n || max(yr - yl, 1) <= xq - xp - 2)) { if (i == 0) s0 = 1, x0 = -(X + 2), y0 = -(X + 2); else s0 = max(max(xp - xl, ypr[i - 1] - ypl[i - 1]), 1), x0 = xp - s0, y0 = ypr[i - 1] - s0; if (j + 1 == n) s2 = 1, x2 = X + 1, y2 = -(X + 2); else s2 = max(max(xr - xq, yqr[j + 1] - yql[j + 1]), 1), x2 = xq, y2 = yqr[j + 1] - s2; s1 = max(max(xt - xs, yr - yl), 1), x1 = min(xs, j + 1 == n ? X + 1 : xq - 1 - s1), y1 = yl; if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(s0, s1), s2)) { xx_[0] = x0, yy_[0] = y0, ss_[0] = s0; xx_[1] = x1, yy_[1] = y1, ss_[1] = s1; xx_[2] = x2, yy_[2] = y2, ss_[2] = s2; } } } void update(int *ft, int i, int n, int x) { while (i < n) { ft[i] = max(ft[i], x); i |= i + 1; } } int query(int *ft, int i) { int x = -1; while (i >= 0) { x = max(x, ft[i]); i &= i + 1, i--; } return x; } void solve111(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) { static int ii1[N], jj1[N], ii2[N], jj2[N], ii_[N], iil[N], iir[N], jj_[N], jjl[N], jjr[N]; static int uu[N], vv[N], ft1[N], ft2[N]; int ni, nj, i, i_, j, j_, y, lower, upper; if (n == 0) { if (max(max(ss_[0], ss_[1]), ss_[2]) > 1) { xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1; xx_[1] = 0, yy_[1] = -(X + 2), ss_[1] = 1; xx_[2] = X + 1, yy_[2] = -(X + 2), ss_[2] = 1; } return; } xl = xx[ii[0]], xr = xx[ii[n - 1]]; yl = X, yr = -X; for (i = 0; i < n; i++) { y = yy[ii[i]]; ypl[i] = yl = min(yl, y); ypr[i] = yr = max(yr, y); } yl = X, yr = -X; for (i = n - 1; i >= 0; i--) { y = yy[ii[i]]; yql[i] = yl = min(yl, y); yqr[i] = yr = max(yr, y); } for (i = 0; i + 1 < n; i++) { xp = xx[ii[i]], xq = xx[ii[i + 1]]; s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1); s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1); if (s0 > s1) break; } i_ = i; yl = X, yr = -X; ysl[i_] = X, ysr[i_] = -X; for (i = i_ - 1; i >= 0; i--) { y = yy[ii[i]]; ysl[i] = yl = min(yl, y); ysr[i] = yr = max(yr, y); } yl = X, yr = -X; for (i = i_; i < n; i++) { y = yy[ii[i]]; ytl[i] = yl = min(yl, y); ytr[i] = yr = max(yr, y); } for (i = i_; i >= 0; i--) try(ii, n, i, n - 1, xx_, yy_, ss_); for (j = i_; j < n; j++) { try(ii, n, 0, j, xx_, yy_, ss_); try(ii, n, i_, j, xx_, yy_, ss_); } ni = 0; for (i = i_ - 1; i > 0; i--) if (xx[ii[i]] > xx[ii[i - 1]]) ii1[ni++] = i; nj = 0; for (j = i_; j + 1 < n; j++) if (xx[ii[j]] < xx[ii[j + 1]]) jj1[nj++] = j; for (i = 0, j = nj - 1; i < ni; i++) { i_ = ii1[i]; while (j > 0) { j_ = jj1[j]; xp = xx[ii[i_ - 1]], xs = xx[ii[i_]]; xt = xx[ii[j_]], xq = xx[ii[j_ + 1]]; yl = min(ysl[i_], ytl[j_]), yr = max(ysr[i_], ytr[j_]); s1 = max(max(xt - xs, yr - yl), 1), s2 = max(max(xr - xq, yqr[j_ + 1] - yql[j_ + 1]), 1); if (s1 <= s2) break; j--; } jj_[i] = j; } for (i = 0, j = 0; i < ni; i++) { i_ = ii1[i]; while (j < nj && ysl[i_] <= ytl[jj1[j]]) j++; jjl[i] = j; } for (i = 0, j = 0; i < ni; i++) { i_ = ii1[i]; while (j < nj && ysr[i_] >= ytr[jj1[j]]) j++; jjr[i] = j; } for (j = 0, i = ni - 1; j < nj; j++) { j_ = jj1[j]; while (i > 0) { i_ = ii1[i]; xp = xx[ii[i_ - 1]], xs = xx[ii[i_]]; xt = xx[ii[j_]], xq = xx[ii[j_ + 1]]; yl = min(ysl[i_], ytl[j_]), yr = max(ysr[i_], ytr[j_]); s1 = max(max(xt - xs, yr - yl), 1), s0 = max(max(xp - xl, ypr[i_ - 1] - ypl[i_ - 1]), 1); if (s1 <= s0) break; i--; } ii_[j] = i; } for (i = 0, j = 0; j < nj; j++) { j_ = jj1[j]; while (i < ni && ytl[j_] <= ysl[ii1[i]]) i++; iil[j] = i; } for (i = 0, j = 0; j < nj; j++) { j_ = jj1[j]; while (i < ni && ytr[j_] >= ysr[ii1[i]]) i++; iir[j] = i; } /* ysl[i_] <= ytl[j_] && ysr[i_] >= ytr[j_] */ for (i = 0; i < ni; i++) { i_ = ii1[i]; lower = -1, upper = min(jjl[i], jjr[i]); while (upper - lower > 1) { j = (lower + upper) / 2, j_ = jj1[j]; if (ysr[i_] - ysl[i_] <= xx[ii[j_ + 1]] - xx[ii[i_ - 1]] - 2) upper = j; else lower = j; } lower = upper, upper = min(jjl[i], jjr[i]) - 1; if (lower > upper) continue; j = jj_[i]; if (j < lower) try(ii, n, i_, jj1[lower], xx_, yy_, ss_); else if (j > upper) try(ii, n, i_, jj1[upper], xx_, yy_, ss_); else try(ii, n, i_, jj1[j], xx_, yy_, ss_); } /* ytl[j_] <= ysl[i_] && ytr[j_] >= ysr[i_] */ for (j = 0; j < nj; j++) { j_ = jj1[j]; lower = -1, upper = min(iil[j], iir[j]); while (upper - lower > 1) { i = (lower + upper) / 2, i_ = ii1[i]; if (ytr[j_] - ytl[j_] <= xx[ii[j_ + 1]] - xx[ii[i_ - 1]] - 2) upper = i; else lower = i; } lower = upper, upper = min(iil[j], iir[j]) - 1; if (lower > upper) continue; i = ii_[j]; if (i < lower) try(ii, n, ii1[lower], j_, xx_, yy_, ss_); else if (i > upper) try(ii, n, ii1[upper], j_, xx_, yy_, ss_); else try(ii, n, ii1[i], j_, xx_, yy_, ss_); } for (i = 0; i < ni; i++) ii2[i] = i; for (j = 0; j < nj; j++) jj2[j] = j; /* ysl[i_] <= ytl[j_] && ysr[i_] < ytr[j_] */ for (i = 0; i < ni; i++) { i_ = ii1[i]; uu[i] = ysl[i_] - (xx[ii[i_ - 1]] + 1); } for (j = 0; j < nj; j++) { j_ = jj1[j]; vv[j] = ytr[j_] - (xx[ii[j_ + 1]] - 1); } zz = uu, sort(ii2, 0, ni); zz = vv, sort(jj2, 0, nj); memset(ft1, -1, nj * sizeof *ft1); memset(ft2, -1, nj * sizeof *ft2); for (i = 0, j = 0; i < ni; i++) { lower = jjr[i], upper = jjl[i] - 1; if (lower > upper) continue; i_ = ii2[i]; while (j < nj && uu[i_] >= vv[j_ = jj2[j]]) update(ft1, j_, nj, j_), update(ft2, nj - 1 - j_, nj, nj - 1 - j_), j++; j_ = query(ft1, min(jj_[i_], upper)); if (j_ >= lower) try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_); j_ = nj - 1 - query(ft2, nj - 1 - max(jj_[i_], lower)); if (j_ <= upper) try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_); } /* ysl[i_] > ytl[j_] && ysr[i_] >= ytr[j_] */ for (i = 0; i < ni; i++) { i_ = ii1[i]; uu[i] = -(ysr[i_] + (xx[ii[i_ - 1]] + 1)); } for (j = 0; j < nj; j++) { j_ = jj1[j]; vv[j] = -(ytl[j_] + (xx[ii[j_ + 1]] - 1)); } zz = uu, sort(ii2, 0, ni); zz = vv, sort(jj2, 0, nj); memset(ft1, -1, nj * sizeof *ft1); memset(ft2, -1, nj * sizeof *ft2); for (i = 0, j = 0; i < ni; i++) { lower = jjl[i], upper = jjr[i] - 1; if (lower > upper) continue; i_ = ii2[i]; while (j < nj && uu[i_] >= vv[j_ = jj2[j]]) update(ft1, j_, nj, j_), update(ft2, nj - 1 - j_, nj, nj - 1 - j_), j++; j_ = query(ft1, min(jj_[i_], upper)); if (j_ >= lower) try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_); j_ = nj - 1 - query(ft2, nj - 1 - max(jj_[i_], lower)); if (j_ <= upper) try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_); } } int main() { static int ii[N]; static long long xx_[3], yy_[3], ss_[3]; int k, h, i, r; long long tmp; scanf("%d%d", &n, &k); for (i = 0; i < n; i++) { scanf("%d%d", &xx[i], &yy[i]); ii[i] = i; } ss_[0] = INF; if (k == 1) solve1(ii, n, xx_, yy_, ss_); else if (k == 2) for (r = 0; r < 2; r++) { zz = xx, sort(ii, 0, n); solve2(ii, n, xx_, yy_, ss_); for (i = 0; i < n; i++) tmp = xx[i], xx[i] = yy[i], yy[i] = tmp; for (h = 0; h < k; h++) tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp; } else if (k == 3) { for (r = 0; r < 4; r++) { zz = xx, sort(ii, 0, n); solve21(ii, n, xx_, yy_, ss_); for (i = 0; i < n; i++) tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp; for (h = 0; h < k; h++) tmp = xx_[h], xx_[h] = -yy_[h], yy_[h] = tmp, xx_[h] -= ss_[h]; } for (r = 0; r < 2; r++) { zz = xx, sort(ii, 0, n); solve111(ii, n, xx_, yy_, ss_); for (i = 0; i < n; i++) tmp = xx[i], xx[i] = yy[i], yy[i] = tmp; for (h = 0; h < k; h++) tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp; } } for (h = 0; h < k; h++) printf("%lld %lld %lld\n", xx_[h], yy_[h], ss_[h]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

izvanzemaljci.c:135:15: warning: built-in function 'y0' declared as non-function [-Wbuiltin-declaration-mismatch]
  135 | long long x0, y0, s0, x1, y1, s1, x2, y2, s2;
      |               ^~
izvanzemaljci.c:135:27: warning: built-in function 'y1' declared as non-function [-Wbuiltin-declaration-mismatch]
  135 | long long x0, y0, s0, x1, y1, s1, x2, y2, s2;
      |                           ^~
izvanzemaljci.c: In function 'main':
izvanzemaljci.c:399:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  399 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:401:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  401 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...