結果
問題 | No.14 最小公倍数ソート |
ユーザー | なお |
提出日時 | 2014-10-07 08:15:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 880 ms / 5,000 ms |
コード長 | 1,415 bytes |
コンパイル時間 | 671 ms |
コンパイル使用メモリ | 69,624 KB |
実行使用メモリ | 4,448 KB |
最終ジャッジ日時 | 2023-08-28 20:12:45 |
合計ジャッジ時間 | 11,778 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 22 ms
4,380 KB |
testcase_04 | AC | 880 ms
4,380 KB |
testcase_05 | AC | 272 ms
4,376 KB |
testcase_06 | AC | 340 ms
4,448 KB |
testcase_07 | AC | 451 ms
4,380 KB |
testcase_08 | AC | 602 ms
4,380 KB |
testcase_09 | AC | 816 ms
4,396 KB |
testcase_10 | AC | 810 ms
4,444 KB |
testcase_11 | AC | 820 ms
4,388 KB |
testcase_12 | AC | 859 ms
4,380 KB |
testcase_13 | AC | 865 ms
4,376 KB |
testcase_14 | AC | 834 ms
4,432 KB |
testcase_15 | AC | 872 ms
4,396 KB |
testcase_16 | AC | 366 ms
4,388 KB |
testcase_17 | AC | 272 ms
4,432 KB |
testcase_18 | AC | 136 ms
4,424 KB |
testcase_19 | AC | 583 ms
4,428 KB |
ソースコード
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) typedef long long ll; int N; int a[10010]; const int GC = 500; int g[GC][GC]; int gcd(int num1, int num2){ if(num2 == 0) return num1; if(num1 < GC && num2 < GC){ if(g[num1][num2]) return g[num1][num2]; return g[num1][num2] = gcd(num2, num1 % num2); } return gcd(num2, num1 % num2); } int lcm(int num1, int num2){ return num1 / gcd(num1, num2) * num2; } int main(){ do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0); cin >> N; if(N > 10000){ cerr << "error" << endl; return 1; } REP(i,N){ cin >> a[i]; if(a[i] > 10000){ cerr << "error" << endl; return 1; } } sort(a+1, a+N); REP(i,N-1){ int k = a[i], mini = -1, minv = 1<<29; for(int j = i+1; j < N; j++){ if(minv < a[j]) break; int lc = lcm(k, a[j]); if(lc < minv || (lc == minv && a[j] < a[mini])){ minv = lc; mini = j; } } if(mini < 0){ cerr << "error" << endl; return 1; } if(mini != i+1){ int v = a[mini]; memmove(a+i+2, a+i+1, (mini-i-1)*sizeof(a[0])); a[i+1] = v; } } REP(i,N-1) cout << a[i] << " "; cout << a[N-1] << endl; return 0; }