結果
問題 |
No.14 最小公倍数ソート
|
ユーザー |
|
提出日時 | 2024-08-04 15:45:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,337 ms / 5,000 ms |
コード長 | 836 bytes |
コンパイル時間 | 2,005 ms |
コンパイル使用メモリ | 197,724 KB |
最終ジャッジ日時 | 2025-02-23 20:59:55 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N); for(auto &a : A) cin >> a; vector<vector<int>> G(10001,vector<int>(10001,1)); for(int i=2; i<=10000; i++){ for(int k=i; k<=10000; k+=i) for(int l=k; l<=10000; l+=i) G.at(k).at(l) = i; } for(int i=1; i<N; i++){ int a = A.at(i-1); int lcm = 1001001001,B = 1001001001,pos = -1; for(int k=i; k<N; k++){ int b = A.at(k); int now = a*b/G.at(min(a,b)).at(max(a,b)); if(now < lcm) lcm = now,B = b,pos = k; else if(now == lcm && b < B) lcm = now,B = b,pos = k; } swap(A.at(i),A.at(pos)); } for(int i=0; i<N; i++) cout << A.at(i) << (i==N-1?"\n":" "); }