제출 #1058641

#제출 시각아이디문제언어결과실행 시간메모리
1058641rainboyText editor (CEOI24_editor)C11
16 / 100
769 ms331948 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1000000 #define N_ (N * 2 + 2) #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3fLL int abs_(int a) { return a > 0 ? a : -a; } int min(int a, int b) { return a < b ? a : b; } int *ej[N_], *ew[N_], eo[N_]; void append(int i, int j, int w) { int o = eo[i]++; if (o >= 2 && (o & o - 1) == 0) { ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]); } ej[i][o] = j, ew[i][o] = w; } long long dd[N_]; int iq[N_ + 1], pq[N_], cnt; int lt(int i, int j) { return dd[i] < dd[j]; } int p2(int p) { return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p); } void pq_up(int i) { int p, q, j; for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_dn(int i) { int p, q, j; for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_add_last(int i) { iq[pq[i] = ++cnt] = i; } int pq_remove_first() { int i = iq[1], j = iq[cnt--]; if (j != i) pq[j] = 1, pq_dn(j); pq[i] = 0; return i; } int main() { static int yy[N], qu[N]; int n, n_, s, t, i, is, it, j, o, y, ys, yt, w, cnt; long long d; scanf("%d%d%d%d%d", &n, &is, &ys, &it, &yt), is--, ys--, it--, yt--; for (i = 0; i < n; i++) scanf("%d", &yy[i]); n_ = n * 2 + 2, s = n_ - 2, t = n_ - 1; for (i = 0; i < n_; i++) { ej[i] = (int *) malloc(2 * sizeof *ej[i]); ew[i] = (int *) malloc(2 * sizeof *ew[i]); } memset(dd, 0x3f, n * sizeof *dd); for (i = is; i >= 0; i--) { if (yy[i] > ys) { append(s, i << 1 | 0, abs_(i - is) + abs_(0 - ys)); append(s, i << 1 | 1, abs_(i - is) + abs_(yy[i] - ys)); if (i == it) append(s, t, abs_(i - is) + abs_(yt - ys)); } else { append(s, i << 1 | 1, abs_(i - is)); break; } } for (i = is; i < n; i++) { if (yy[i] > ys) { append(s, i << 1 | 0, abs_(i - is) + abs_(0 - ys)); append(s, i << 1 | 1, abs_(i - is) + abs_(yy[i] - ys)); if (i == it) append(s, t, abs_(i - is) + abs_(yt - ys)); } else { append(s, i << 1 | 1, abs_(i - is)); break; } } for (i = 0; i < n; i++) append(i << 1 | 0, i << 1 | 1, yy[i]), append(i << 1 | 1, i << 1 | 0, yy[i]); for (i = 0; i + 1 < n; i++) { append(i << 1 | 0, i + 1 << 1 | 0, 1), append(i + 1 << 1 | 0, i << 1 | 0, 1); append(i << 1 | 1, i + 1 << 1 | 0, 1), append(i + 1 << 1 | 0, i << 1 | 1, 1); } cnt = 0; for (j = 0; j < n; j++) { while (cnt && yy[qu[cnt - 1]] > yy[j]) cnt--; if (cnt) { i = qu[cnt - 1]; append(j << 1 | 1, i << 1 | 1, abs_(i - j)); append(i << 1 | 1, j << 1 | 1, abs_(j - i) + abs_(yy[j] - yy[i])); } qu[cnt++] = j; } cnt = 0; for (i = n - 1; i >= 0; i--) { while (cnt && yy[qu[cnt - 1]] > yy[j]) cnt--; if (cnt) { j = qu[cnt - 1]; append(i << 1 | 1, j << 1 | 1, abs_(j - i)); append(j << 1 | 1, i << 1 | 1, abs_(i - j) + abs_(yy[i] - yy[j])); } qu[cnt++] = i; } y = INF; for (i = it; i >= 0; i--) { append(i << 1 | 0, t, abs_(it - i) + abs_(yt - 0)); if (y > yy[i]) y = yy[i], append(i << 1 | 1, t, abs_(it - i) + abs_(yt - yy[i])); } y = INF; for (i = it; i < n; i++) { append(i << 1 | 0, t, abs_(it - i) + abs_(yt - 0)); if (y > yy[i]) y = yy[i], append(i << 1 | 1, t, abs_(it - i) + abs_(yt - yy[i])); } memset(dd, 0x3f, n_ * sizeof *dd); dd[s] = 0, pq_add_last(s); while (cnt) { i = pq_remove_first(); if (i == t) { printf("%lld\n", dd[i]); return 0; } for (o = eo[i]; o--; ) { j = ej[i][o], w = ew[i][o], d = dd[i] + w; if (dd[j] > d) { if (dd[j] == LINF) pq_add_last(j); dd[j] = d, pq_up(j); } } } return 0; }

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

Main.c: In function 'append':
Main.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Main.c: In function 'main':
Main.c:101:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  101 |   append(i << 1 | 0, i + 1 << 1 | 0, 1), append(i + 1 << 1 | 0, i << 1 | 0, 1);
      |                      ~~^~~
Main.c:101:51: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  101 |   append(i << 1 | 0, i + 1 << 1 | 0, 1), append(i + 1 << 1 | 0, i << 1 | 0, 1);
      |                                                 ~~^~~
Main.c:102:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  102 |   append(i << 1 | 1, i + 1 << 1 | 0, 1), append(i + 1 << 1 | 0, i << 1 | 1, 1);
      |                      ~~^~~
Main.c:102:51: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  102 |   append(i << 1 | 1, i + 1 << 1 | 0, 1), append(i + 1 << 1 | 0, i << 1 | 1, 1);
      |                                                 ~~^~~
Main.c:67:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d%d%d%d%d", &n, &is, &ys, &it, &yt), is--, ys--, it--, yt--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:69:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d", &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...
#Verdict Execution timeMemoryGrader output
Fetching results...