結果
問題 | No.1816 MUL-DIV Game |
ユーザー |
👑 |
提出日時 | 2022-01-21 21:29:33 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 3,479 bytes |
コンパイル時間 | 1,387 ms |
コンパイル使用メモリ | 30,592 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-25 22:41:41 |
合計ジャッジ時間 | 2,691 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <stdio.h>typedef struct {long long key;int id;} data;typedef struct {data obj[100001];int size;} min_max_heap;long long get_min(min_max_heap* h){return h->obj[0].key;}int get_argmin(min_max_heap* h){return h->obj[0].id;}long long get_max(min_max_heap* h){if (h->size == 1) return h->obj[0].key;else return h->obj[1].key;}int get_argmax(min_max_heap* h){if (h->size == 1) return h->obj[0].id;else return h->obj[1].id;}void push(min_max_heap* h, data x){int i = (h->size)++;data tmp;if ((i & 1) != 0 && x.key < h->obj[i^1].key) {h->obj[i] = h->obj[i^1];h->obj[i^1] = x;i ^= 1;} else h->obj[i] = x;int j, k = ((i >> 1) + 1) >> 1;if (k == 0) return;j = (k - 1) << 1;if (h->obj[i].key < h->obj[j].key) {while (k > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = (k - 1) << 1;} else break;}} else if (h->obj[i].key > h->obj[j^1].key) {j ^= 1;while (k > 0) {if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = ((k - 1) << 1) ^ 1;} else break;}}}data pop_min(min_max_heap* h){int i = 0, j = 2, k = 2;data output = h->obj[0], tmp;h->obj[0] = h->obj[--(h->size)];while (j < h->size) {if (j + 2 < h->size && h->obj[j+2].key < h->obj[j].key) {j += 2;k++;}if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k <<= 1;i = j;j = (k - 1) << 1;} else break;}if (j < h->size) return output;if (i < h->size - 1 && h->obj[i].key > h->obj[i^1].key) {tmp = h->obj[i^1];h->obj[i^1] = h->obj[i];h->obj[i] = tmp;i ^= 1;}k = ((i >> 1) + 1) >> 1;j = ((k - 1) << 1) ^ 1;while (k > 0) {if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = ((k - 1) << 1) ^ 1;} else break;}return output;}data pop_max(min_max_heap* h){if (h->size == 1) return h->obj[--(h->size)];int i = 1, j = 2, k = 2;data output = h->obj[1], tmp;h->obj[1] = h->obj[--(h->size)];while (j < h->size) {if (j + 1 < h->size) {j++;if (j + 2 < h->size && h->obj[j+2].key > h->obj[j].key) {j += 2;k++;} else if (j + 1 < h->size && h->obj[j+1].key > h->obj[j].key) {j++;k++;}}if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k <<= 1;i = j;j = (k - 1) << 1;} else break;}if (j < h->size) return output;i = (i >> 1) << 1;if (i < h->size - 1 && h->obj[i].key > h->obj[i^1].key) {tmp = h->obj[i^1];h->obj[i^1] = h->obj[i];h->obj[i] = tmp;}k = ((i >> 1) + 1) >> 1;j = (k - 1) << 1;while (k > 0) {if (h->obj[i].key < h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;k >>= 1;i = j;j = (k - 1) << 1;} else break;}return output;}int main(){int i, N;data d;min_max_heap h;h.size = 0;scanf("%d", &N);for (i = 1; i <= N; i++) {scanf("%d", &(d.key));push(&h, d);}for (i = 1; i < N; i++) {if (i % 2 == 0) {pop_max(&h);pop_max(&h);d.key = 1;push(&h, d);} else {d = pop_min(&h);d.key *= pop_min(&h).key;push(&h, d);}}printf("%lld\n", get_max(&h));fflush(stdout);return 0;}