結果
問題 | No.1795 AtCoder Heuristic Rating coloring |
ユーザー |
![]() |
提出日時 | 2022-01-16 15:01:24 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 1,502 bytes |
コンパイル時間 | 441 ms |
コンパイル使用メモリ | 31,104 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-11-23 10:39:45 |
合計ジャッジ時間 | 6,213 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 54 |
ソースコード
#include<stdio.h>char s[100005][32];int h[100005], l;int strcmp(char s[], char t[]){int i;for (i = 0;; i++){if (s[i] == '\0' && t[i] == '\0')return 0;if (s[i] == '\0')return -1;if (t[i] == '\0')return 1;if (s[i] > t[i])return 1;if (s[i] < t[i])return -1;}}int comp_h(int a, int b){if (strcmp(s[h[a]], s[h[b]]) != 0)return strcmp(s[h[a]], s[h[b]]);else if (h[a] > h[b])return -1;elsereturn 1;}void swap_h(int a, int b){int f = h[a];h[a] = h[b];h[b] = f;return;}void push(int ne){h[l] = ne;int p = l;l++;for (; p > 0; p = (p - 1) / 2)if (comp_h((p - 1) / 2, p) > 0)swap_h((p - 1) / 2, p);return;}int pop(){l--;swap_h(0, l);int p = 0;for (;;){if (2 * p + 2 < l){if (comp_h(2 * p + 1, 2 * p + 2) > 0){if (comp_h(p, 2 * p + 2) > 0)swap_h(p, 2 * p + 2);p = 2 * p + 2;}else{if (comp_h(p, 2 * p + 1) > 0)swap_h(p, 2 * p + 1);p = 2 * p + 1;}}else if (2 * p + 1 < l){if (comp_h(p, 2 * p + 1) > 0)swap_h(p, 2 * p + 1);p = 2 * p + 1;}elsebreak;}return h[l];}int main(){int n, m;scanf("%d %d", &n, &m);int a[100005];int i, j;for (i = 0; i < n + m; i++)scanf("%s%d", s[i], &a[i]);l = 0;for (i = 0; i < n + m; i++)push(i);j = pop();printf("%s %d\n", s[j], a[j]);while (l > 0){i = pop();if (strcmp(s[j], s[i]) != 0)printf("%s %d\n", s[i], a[i]);j = i;}return 0;}