結果

問題 No.14 最小公倍数ソート
ユーザー Unbakedbread
提出日時 2025-08-14 17:03:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 36 ms / 5,000 ms
コード長 824 bytes
コンパイル時間 3,963 ms
コンパイル使用メモリ 286,660 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2025-08-14 17:03:09
合計ジャッジ時間 5,929 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int M=10000;

int main(){
	int n;cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	
	vector<int> cnt(M+1,0);
	for(int i=1;i<n;i++) cnt[a[i]]++;
	
	vector<vector<int>> divs(M+1,{1});
	for(int i=2;i<=M;i++) for(int j=i;j<=M;j+=i) divs[j].push_back(i);
	for(int i=1;i<=M;i++) reverse(divs[i].begin(),divs[i].end());
	
	vector<set<int>> s(M+1);
	for(int i=1;i<=M;i++) if(cnt[i]!=0) for(auto d:divs[i]) s[d].insert(i);
	
	int now=a[0];
	cout<<now<<" ";
	while(!s[1].empty()){
		int lcm=1e9,t=1e9;
		for(auto d:divs[now]){
			if(s[d].empty()) continue;
			int v=*s[d].begin();
			if(lcm>=v*now/d){
				lcm=v*now/d;
				t=min(t,v);
			}
		}
		if(t==1e9) break;
		now=t;
		while(cnt[t]--) cout<<t<<" ";
		for(auto d:divs[t]) s[d].erase(t);
	}
	cout<<"\n";
	return 0;
}
0