結果

問題 No.14 最小公倍数ソート
ユーザー ゴリポン先生
提出日時 2025-05-18 16:55:41
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 82 ms / 5,000 ms
コード長 1,055 bytes
コンパイル時間 7,774 ms
コンパイル使用メモリ 234,020 KB
実行使用メモリ 12,132 KB
最終ジャッジ日時 2025-05-18 16:55:52
合計ジャッジ時間 10,117 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://yang33-kassa.jp/yukicoder/yukicoder014/ より
import std;

void main()
{
	immutable INF = 10 ^^ 9;
	// 入力
	int N = readln.chomp.to!int;
	auto A = readln.split.to!(int[]);
	// 答えの計算と出力
	auto divs = new int[][](N);
	alias P = Tuple!(int, int);
	auto S = new RedBlackTree!(P)[](10_001);
	foreach (ref s; S)
		s = new RedBlackTree!P();
	foreach (i; 0 .. N) {
		for (int j = 1; j * j <= A[i]; j++) {
			if (A[i] % j) continue;
			divs[i] ~= j;
			S[j].insert(P(A[i], i));
			if (j * j != A[i]) {
				divs[i] ~= A[i] / j;
				S[A[i] / j].insert(P(A[i], i));
			}
		}
	}
	int id = 0;
	foreach (_; 0 .. N) {
		write(A[id], _ == N - 1 ? "\n" : " ");

		P Min = P(INF, INF);
		int tmpId = -1;
		foreach (i; 0 .. divs[id].length.to!int) {
			S[divs[id][i]].removeKey(P(A[id], id));	// 使ってはいけないので
			if (S[divs[id][i]].empty) continue;
			P b = S[divs[id][i]].front;
			P comp = P(A[id] / divs[id][i] * A[b[1]], b[0]);
			if (Min > comp) {
				Min = comp;
				tmpId = b[1];
			}
		}
		id = tmpId;
	}
}
0