結果
問題 | No.649 ここでちょっとQK! |
ユーザー | akakimidori |
提出日時 | 2019-05-26 20:13:08 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 90 ms / 3,000 ms |
コード長 | 4,329 bytes |
コンパイル時間 | 209 ms |
コンパイル使用メモリ | 32,516 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-17 18:03:14 |
合計ジャッジ時間 | 3,272 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 23 ms
4,348 KB |
testcase_04 | AC | 88 ms
4,348 KB |
testcase_05 | AC | 90 ms
4,348 KB |
testcase_06 | AC | 61 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,348 KB |
testcase_09 | AC | 1 ms
4,348 KB |
testcase_10 | AC | 1 ms
4,348 KB |
testcase_11 | AC | 1 ms
4,348 KB |
testcase_12 | AC | 41 ms
4,348 KB |
testcase_13 | AC | 37 ms
4,348 KB |
testcase_14 | AC | 37 ms
4,348 KB |
testcase_15 | AC | 46 ms
4,348 KB |
testcase_16 | AC | 33 ms
4,348 KB |
testcase_17 | AC | 43 ms
4,348 KB |
testcase_18 | AC | 48 ms
4,348 KB |
testcase_19 | AC | 55 ms
4,348 KB |
testcase_20 | AC | 58 ms
4,348 KB |
testcase_21 | AC | 65 ms
4,348 KB |
testcase_22 | AC | 68 ms
4,348 KB |
testcase_23 | AC | 76 ms
4,348 KB |
testcase_24 | AC | 79 ms
4,348 KB |
testcase_25 | AC | 85 ms
4,348 KB |
testcase_26 | AC | 90 ms
4,348 KB |
testcase_27 | AC | 1 ms
4,348 KB |
testcase_28 | AC | 1 ms
4,348 KB |
testcase_29 | AC | 1 ms
4,348 KB |
testcase_30 | AC | 36 ms
4,348 KB |
testcase_31 | AC | 31 ms
4,348 KB |
testcase_32 | AC | 1 ms
4,348 KB |
testcase_33 | AC | 1 ms
4,348 KB |
testcase_34 | AC | 1 ms
4,348 KB |
testcase_35 | AC | 1 ms
4,348 KB |
ソースコード
#include<stdio.h> #include<stdlib.h> #include<stdint.h> #include<inttypes.h> typedef struct binaryHeap{ void *array; size_t heap_size; size_t max_size; size_t val_size; int (*cmp) (const void *, const void *); } heap; heap* new_binary_heap (const size_t val_size, int (*cmpF) (const void *, const void *)) { heap *h = (heap *) calloc (1, sizeof (heap)); h->array = malloc (val_size * (1 + 1)); h->heap_size = 0; h->max_size = 1; h->val_size = val_size; h->cmp = cmpF; return h; } int32_t get_heap_size (const heap *h) { return h->heap_size; } int is_empty (const heap *h) { return h->heap_size == 0; } void free_heap (heap *h) { free (h->array); free (h); } void init_heap (heap *h) { h->heap_size = 0; } static inline void heap_func_swap (void * restrict a, void * restrict b, size_t val_size) { if ((val_size & 7) == 0) { uint64_t *p = (uint64_t *) a; uint64_t *q = (uint64_t *) b; val_size /= sizeof (uint64_t); while (val_size--) { const uint64_t tmp = *p; *p++ = *q; *q++ = tmp; } } else { uint8_t *p = (uint8_t *) a; uint8_t *q = (uint8_t *) b; while (val_size--) { const uint8_t tmp = *p; *p++ = *q; *q++ = tmp; } } } static inline void heap_func_copy (void * restrict dst, const void * restrict src, size_t val_size) { if ((val_size & 7) == 0) { const uint64_t *p = (const uint64_t *) src; uint64_t *q = (uint64_t *) dst; val_size /= sizeof (uint64_t); while (val_size--) { *q++ = *p++; } } else { const uint8_t *p = (const uint8_t *) src; uint8_t *q = (uint8_t *) dst; while (val_size--) { *q++ = *p++; } } } void push (heap * const h, const void *val) { if (h->heap_size == h->max_size) { h->max_size = 2 * h->max_size + 1; h->array = realloc (h->array, h->val_size * (h->max_size + 1)); } h->heap_size++; uint8_t * const array = (uint8_t *) h->array; size_t k = h->heap_size; const size_t val_size = h->val_size; int (* const cmp) (const void *, const void *) = h->cmp; heap_func_copy(array + k * val_size, val, val_size); while (k > 1) { size_t parent = k / 2; if (cmp (array + parent * val_size, array + k * val_size) <= 0) { return; } heap_func_swap (array + parent * val_size, array + k * val_size, val_size); k = parent; } } void pop (heap * const h, void *res) { uint8_t * const array = (uint8_t *) h->array; const size_t val_size = h->val_size; if (res != NULL) { heap_func_copy (res, array + val_size, val_size); } heap_func_copy (array + val_size, array + val_size * h->heap_size, val_size); h->heap_size--; int (* const cmp) (const void *, const void *) = h->cmp; const size_t n = h->heap_size; size_t k = 1; while (2 * k + 1 <= n) { const int c = cmp (array + val_size * 2 * k, array + val_size * (2 * k + 1)); const size_t next = 2 * k + (c <= 0 ? 0 : 1); if (cmp (array + val_size * k, array + val_size * next) <= 0) return; heap_func_swap (array + val_size * k, array + val_size * next, val_size); k = next; } if (2 * k <= n && cmp (array + val_size * k, array + val_size * 2 * k) > 0) { heap_func_swap (array + val_size * k, array + val_size * 2 * k, val_size); } } void top (const heap *h, void *res) { uint8_t *array = (uint8_t *) h->array; const size_t val_size = h->val_size; if (res != NULL) { heap_func_copy (res, array + val_size, val_size); } } typedef int32_t i32; typedef int64_t i64; int cmp_min (const void *a, const void *b) { i64 d = *(i64 *)a - *(i64 *)b; return d == 0 ? 0 : d < 0 ? -1 : 1; } int cmp_max (const void *a, const void *b) { return - cmp_min (a, b); } void run (void) { i32 q, k; scanf ("%" SCNi32 "%" SCNi32, &q, &k); heap *small = new_binary_heap (sizeof (i64), cmp_max); heap *large = new_binary_heap (sizeof (i64), cmp_min); while (q--) { i32 op; scanf ("%" SCNi32, &op); if (op == 1) { i64 v; scanf ("%" SCNi64, &v); push (small, &v); if (get_heap_size (small) < k) continue; pop (small, &v); push (large, &v); } else if (is_empty (large)) { puts ("-1"); } else { i64 v; pop (large, &v); printf ("%" PRIi64 "\n", v); } } } int main (void) { run(); return 0; }