結果
問題 | No.738 平らな農地 |
ユーザー | bal4u |
提出日時 | 2019-08-05 07:43:27 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,430 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 32,980 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-18 10:35:32 |
合計ジャッジ時間 | 3,291 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 12 ms
5,376 KB |
testcase_16 | AC | 12 ms
5,376 KB |
testcase_17 | AC | 11 ms
5,376 KB |
testcase_18 | AC | 12 ms
5,376 KB |
testcase_19 | AC | 13 ms
5,376 KB |
testcase_20 | AC | 13 ms
5,376 KB |
testcase_21 | AC | 13 ms
5,376 KB |
testcase_22 | AC | 12 ms
5,376 KB |
testcase_23 | AC | 12 ms
5,376 KB |
testcase_24 | AC | 11 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 1 ms
5,376 KB |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 1 ms
5,376 KB |
testcase_31 | AC | 0 ms
5,376 KB |
testcase_32 | AC | 1 ms
5,376 KB |
testcase_33 | AC | 1 ms
5,376 KB |
testcase_34 | AC | 1 ms
5,376 KB |
testcase_35 | AC | 1 ms
5,376 KB |
testcase_36 | AC | 1 ms
5,376 KB |
testcase_37 | AC | 1 ms
5,376 KB |
testcase_38 | AC | 1 ms
5,376 KB |
testcase_39 | AC | 1 ms
5,376 KB |
testcase_40 | AC | 0 ms
5,376 KB |
testcase_41 | AC | 1 ms
5,376 KB |
testcase_42 | AC | 1 ms
5,376 KB |
testcase_43 | AC | 1 ms
5,376 KB |
testcase_44 | AC | 1 ms
5,376 KB |
testcase_45 | AC | 14 ms
5,376 KB |
testcase_46 | AC | 13 ms
5,376 KB |
testcase_47 | AC | 13 ms
5,376 KB |
testcase_48 | AC | 14 ms
5,376 KB |
testcase_49 | AC | 13 ms
5,376 KB |
testcase_50 | AC | 14 ms
5,376 KB |
testcase_51 | AC | 14 ms
5,376 KB |
testcase_52 | AC | 13 ms
5,376 KB |
testcase_53 | AC | 13 ms
5,376 KB |
testcase_54 | AC | 13 ms
5,376 KB |
testcase_55 | AC | 13 ms
5,376 KB |
testcase_56 | AC | 13 ms
5,376 KB |
testcase_57 | AC | 13 ms
5,376 KB |
testcase_58 | AC | 14 ms
5,376 KB |
testcase_59 | AC | 14 ms
5,376 KB |
testcase_60 | AC | 15 ms
5,376 KB |
testcase_61 | AC | 15 ms
5,376 KB |
testcase_62 | AC | 13 ms
5,376 KB |
testcase_63 | AC | 14 ms
5,376 KB |
testcase_64 | AC | 13 ms
5,376 KB |
testcase_65 | AC | 1 ms
5,376 KB |
testcase_66 | AC | 1 ms
5,376 KB |
testcase_67 | AC | 11 ms
5,376 KB |
testcase_68 | AC | 11 ms
5,376 KB |
testcase_69 | AC | 12 ms
5,376 KB |
testcase_70 | AC | 12 ms
5,376 KB |
testcase_71 | AC | 2 ms
5,376 KB |
testcase_72 | AC | 5 ms
5,376 KB |
testcase_73 | AC | 5 ms
5,376 KB |
testcase_74 | AC | 4 ms
5,376 KB |
testcase_75 | AC | 15 ms
5,376 KB |
testcase_76 | AC | 12 ms
5,376 KB |
testcase_77 | AC | 16 ms
5,376 KB |
testcase_78 | AC | 18 ms
5,376 KB |
testcase_79 | WA | - |
testcase_80 | WA | - |
testcase_81 | AC | 13 ms
5,376 KB |
testcase_82 | AC | 10 ms
5,376 KB |
testcase_83 | AC | 4 ms
5,376 KB |
testcase_84 | AC | 14 ms
5,376 KB |
testcase_85 | AC | 4 ms
5,376 KB |
testcase_86 | AC | 12 ms
5,376 KB |
testcase_87 | AC | 16 ms
5,376 KB |
testcase_88 | AC | 15 ms
5,376 KB |
testcase_89 | AC | 1 ms
5,376 KB |
testcase_90 | AC | 1 ms
5,376 KB |
testcase_91 | AC | 1 ms
5,376 KB |
コンパイルメッセージ
main.c: In function 'in': main.c:11:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 11 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:17:24: note: in expansion of macro 'gc' 17 | int n = 0, c = gc(); | ^~
ソースコード
// yukicoder: No.738 平らな農地// 2019.8.4 bal4u#include <stdio.h>#include <stdlib.h>#include <string.h>typedef long long ll;#if 1#define gc() getchar_unlocked()#else#define gc() getchar()#endifint in() { // 非負整数の入力int n = 0, c = gc();do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');return n;}#define MAX 100005typedef struct { int v, id; } QUE;QUE qmin[MAX]; int szqmin;QUE qmax[MAX]; int szqmax;#define PARENT(i) ((i)>>1)#define LEFT(i) ((i)<<1)#define RIGHT(i) (((i)<<1)+1)void min_heapify(int i) {int l, r, min;l = LEFT(i), r = RIGHT(i);if (l < szqmin && (qmin[l].v < qmin[i].v ||(qmin[l].v == qmin[i].v && qmin[l].id < qmin[i].id))) min = l; else min = i;if (r < szqmin && (qmin[r].v < qmin[min].v ||(qmin[r].v == qmin[min].v && qmin[r].id < qmin[min].id))) min = r;if (min != i) {QUE qt = qmin[i]; qmin[i] = qmin[min]; qmin[min] = qt;min_heapify(min);}}int deqmin() {qmin[0] = qmin[--szqmin];min_heapify(0);return 1;}void enqmin(int id, int v) {int i, min;i = szqmin++;qmin[i].id = id, qmin[i].v = v;while (i > 0 && (qmin[min = PARENT(i)].v > qmin[i].v ||(qmin[min].v == qmin[i].v && qmin[min].id > qmin[i].id))) {QUE qt = qmin[i]; qmin[i] = qmin[min]; qmin[min] = qt;i = min;}}void max_heapify(int i) {int l, r, max;l = LEFT(i), r = RIGHT(i);if (l < szqmax && (qmax[l].v > qmax[i].v ||(qmax[l].v == qmax[i].v && qmax[l].id < qmax[i].id))) max = l; else max = i;if (r < szqmax && (qmax[r].v > qmax[max].v ||(qmax[r].v == qmax[max].v && qmax[r].id < qmax[max].id))) max = r;if (max != i) {QUE qt = qmax[i]; qmax[i] = qmax[max], qmax[max] = qt;max_heapify(max);}}void deqmax() {qmax[0] = qmax[--szqmax];max_heapify(0);}void enqmax(int id, int v) {int i, max;i = szqmax++;qmax[i].id = id, qmax[i].v = v;while (i > 0 && (qmax[max = PARENT(i)].v < qmax[i].v ||(qmax[max].v == qmax[i].v && qmax[max].id > qmax[i].id))) {QUE qt = qmax[i]; qmax[i] = qmax[max], qmax[max] = qt;i = max;}}#define ABS(x) ((x)>=0?(x):-(x))int N;int a[MAX]; QUE b[MAX];int cmp(const void *a, const void *b) {int t = ((QUE *)a)->v - ((QUE *)b)->v;if (t) return t;return ((QUE *)a)->id - ((QUE *)b)->id;}int main(){int i, K, k, m, pm, ngmin, ngmax, diff;ll smin, smax, ans, t;N = in(), K = in(), k = K >> 1;if (K == 1) { puts("0"); return 0; }#if 1if (K == 2) {m = in(), ans = 0x7fffffff;while (--N) {pm = m, m = in();if ((t = ABS(pm-m)) < ans) ans = t;}goto done;}#endiffor (i = 0; i < N; i++) a[i] = in();for (i = 0; i < K; i++) b[i].v = a[i], b[i].id = i;qsort(b, K, sizeof(QUE), cmp);m = b[k].v, smin = smax = 0, ngmin = ngmax = 0;for (i = 0; i < k; i++) enqmax(b[i].id, b[i].v), smax += m-b[i].v;for ( ; i < K; i++) enqmin(b[i].id, b[i].v), smin += b[i].v-m;ans = smin + smax; if (ans == 0) goto done;// printf("K=%d, k=%d, m=%d, szqmin=%d, szqmax=%d, smin=%lld, smax=%lld, ans=%lld\n",// K, k, m, szqmin, szqmax, smin, smax, ans);for (i = K; i < N; i++) {int x = a[i-K];if (x > qmin[0].v) ngmin++, smin -= x-m;else if (x < qmax[0].v) ngmax++, smax -= m-x;else if (i-K == qmin[0].id) deqmin(), smin -= x-m;else if (i-K == qmax[0].id) deqmax(), smax -= m-x;else { printf("Panic median=%d, a[%]=%d\n", m, i-K, a[i-K]); return 0; }//printf("szqmin=%d, ngmin=%d, smin=%lld, sqzmax=%d, ngmax=%d, smax=%lld\n",// szqmin, ngmin, smin, szqmax, ngmax, smax);if (a[i] >= m) enqmin(i, a[i]), smin += a[i]-m;else enqmax(i, a[i]), smax += m-a[i];while (1) {QUE qt;diff = (szqmin-ngmin) - (szqmax-ngmax);//printf("a[%d]=%d, diff=%d\n", i, a[i], diff);if (K & 1) {if (diff == 1) break;} else if (diff == 0) break;if (diff > 0) {qt = qmin[0], deqmin();if (qt.id <= i-K) ngmin--;else enqmax(qt.id, qt.v), smin -= qt.v-m, smax += m-qt.v;} else {qt = qmax[0], deqmax();if (qt.id <= i-K) ngmax--;else enqmin(qt.id, qt.v), smin += qt.v-m, smax -= m-qt.v;}}pm = m;if (diff >= 0) m = qmin[0].v; else m = qmax[0].v;if (m != pm) smin += (pm-m) * (szqmin-ngmin), smax += (m-pm)*(szqmax-ngmax);t = smin + smax; if (t < ans) { ans = t; if (ans == 0) goto done; }//printf("pm=%d, m=%d, smin=%lld, smax=%lld, t=%lld, ans=%lld\n\n", pm,m,smin,smax,t,ans);}done:printf("%lld\n", ans);return 0;}