結果

問題 No.205 マージして辞書順最小
ユーザー bal4ubal4u
提出日時 2019-04-15 19:08:06
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,696 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 30,404 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-22 06:45:50
合計ジャッジ時間 1,414 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 1 ms
4,348 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 1 ms
4,348 KB
testcase_11 AC 1 ms
4,348 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 1 ms
4,348 KB
testcase_17 WA -
testcase_18 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:16:24: note: in expansion of macro 'gc'
   16 |         int n = 0, c = gc();
      |                        ^~
main.c: In function 'outs':
main.c:9:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
    9 | #define pc(c) putchar_unlocked(c)
      |               ^~~~~~~~~~~~~~~~
main.c:30:33: note: in expansion of macro 'pc'
   30 | void outs(char *s) { while (*s) pc(*s++); }
      |                                 ^~

ソースコード

diff # 

// yukicoder: No.205 マージして辞書順最小
// 2019.4.15 bal4u

#include <stdio.h>

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in()    // 非負整数の入力
{
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

int ins(char *s)  // 文字列の入力　スペース以下の文字で入力終了
{
	char *p = s;
	do *s = gc();
	while (*s++ > ' ');
	*--s = 0;
	return s - p;
}

void outs(char *s) { while (*s) pc(*s++); }

//// 優先度付きキュー
#define MAX 10000
typedef struct { int id; char c; } QUE;
QUE que[MAX]; int qsize;

#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;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].c < que[i].c) min = l; else min = i;
	if (r < qsize && que[r].c < que[min].c) min = r;
	if (min != i) {
		qt = que[i]; que[i] = que[min]; que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
	que[0] = que[--qsize];
	min_heapify(0);
}

void enq(int id, char c)
{
	int i, min;
	QUE qt;

	i = qsize++;
	que[i].id = id, que[i].c = c;
	while (i > 0 && que[min = PARENT(i)].c > que[i].c) {
		qt = que[i]; que[i] = que[min]; que[min] = qt;
		i = min;
	}
}

int N;
char S[55][55]; int w[55], top[55];
char ans[3000]; int sz;

int main()
{
	int i, c, N;

	N = in();
	for (i = 0; i < N; i++) {
		w[i] = ins(S[i]);
		enq(i, S[i][0]), top[i] = 1;
	}
	while (qsize) {
		c = que[0].c, i = que[0].id, deq();
		ans[sz++] = c;
		if (top[i] < w[i]) enq(i, S[i][top[i]++]);
	}
	ans[sz] = 0, outs(ans), pc('\n');
	return 0;
}
0