結果
問題 | No.14 最小公倍数ソート |
ユーザー | SakaTaku |
提出日時 | 2020-09-21 17:21:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 54 ms / 5,000 ms |
コード長 | 1,251 bytes |
コンパイル時間 | 2,159 ms |
コンパイル使用メモリ | 206,532 KB |
実行使用メモリ | 12,580 KB |
最終ジャッジ日時 | 2023-09-06 17:20:48 |
合計ジャッジ時間 | 3,719 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
8,040 KB |
testcase_01 | AC | 4 ms
8,036 KB |
testcase_02 | AC | 5 ms
8,148 KB |
testcase_03 | AC | 8 ms
8,460 KB |
testcase_04 | AC | 53 ms
12,572 KB |
testcase_05 | AC | 28 ms
10,584 KB |
testcase_06 | AC | 31 ms
10,864 KB |
testcase_07 | AC | 36 ms
11,280 KB |
testcase_08 | AC | 42 ms
11,740 KB |
testcase_09 | AC | 49 ms
12,268 KB |
testcase_10 | AC | 48 ms
12,340 KB |
testcase_11 | AC | 53 ms
12,420 KB |
testcase_12 | AC | 51 ms
12,536 KB |
testcase_13 | AC | 54 ms
12,448 KB |
testcase_14 | AC | 50 ms
12,408 KB |
testcase_15 | AC | 52 ms
12,580 KB |
testcase_16 | AC | 31 ms
10,784 KB |
testcase_17 | AC | 26 ms
10,380 KB |
testcase_18 | AC | 19 ms
9,592 KB |
testcase_19 | AC | 40 ms
11,656 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < n; ++i) using ll = long long; using P = pair<int,int>; multiset<int> A[100001]; int main() { int N;cin>>N; vector<int>a(N); rep(i,N)cin>>a[i]; rep(i,N){ int ai=a[i]; for (int j = 1; j*j <= ai; j++){ if(ai%j==0){ A[j].insert(ai/j); if(j*j==ai)continue; A[ai/j].insert(j); } } } vector<int> ans; ans.push_back(a[0]); rep(i,N-1){ int ai=ans[i]; int mini=1e9, next; int j=1; for (; j*j <= ai; j++){ if(ai%j==0){ A[j].extract(ai/j); if(!A[j].empty()){ if(mini>*A[j].begin()){ mini=*A[j].begin(); next=mini*j; } } } } j--; if(j*j==ai)j--; for (; j*j >= 1; j--){ if(ai%j==0){ int bi=ai/j; A[bi].extract(j); if(!A[bi].empty()){ if(mini>*A[bi].begin()){ mini=*A[bi].begin(); next=mini*bi; } } } } ans.push_back(next); } rep(i,N)cout<<ans[i]<<" "; cout<<endl; }