結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー ktg
提出日時 2016-04-26 23:10:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,472 bytes
コンパイル時間 592 ms
コンパイル使用メモリ 81,532 KB
実行使用メモリ 10,020 KB
最終ジャッジ日時 2024-10-04 15:57:20
合計ジャッジ時間 7,348 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 3 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <iterator>

//#define pb push_back
//#define puts(x) cout << #x << " : " << x << endl;
//#pragma GCC diagnostic ignored "-Wconversion"
//#define REP(i,n) for (int i=0;i<(n);i++)
//#define REPE(i,n) for (int i=0;i<=(n);i++)
//#define init(a,b) memset((a), (b), (sizeof(a)));
//#define PI 3.14159265
//#define EPS (1e-10)
//#define EQ(a,b) (abs((a)-(b)) < EPS)

using namespace std;

typedef long long ll;
//#define int long long

int dxy[] = {0, 1, 0, -1, 0};

typedef pair<int, int> P;
/**
 * 最大公約数
 * GCD
 */
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

/**
 * 最小公倍数
 * LCM
 */
ll lcm(ll a , ll b) {
    return a / (gcd(a, b)) * b;
}

int a[10005];

signed main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n - 1;i++){
        int min_index = i + 1;
        ll min_t = a[i + 1];
        for(int j = i + 2; j<n; j++){
            ll t = lcm(a[i], a[j]);
            if( ( min_t == t && a[min_index] > a[j] ) || (min_t > t) ){
                min_t = t;
                min_index = j;
            }
        }
        swap(a[i + 1], a[min_index]);
    }
    for(int i=0;i<n;i++){
        if(i>0)cout<<' ';
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}
0