#737792 (C++17(clang)) No.14 最小公倍数ソート

• 問題: No.14 最小公倍数ソート
• ユーザー: siman
• 提出日時: 2022-02-08 14:40:40
• 言語: C++17(clang) (17.0.6 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,111 ms / 5,000 ms
• コード長: 951 bytes
• コンパイル時間: 3,420 ms
• コンパイル使用メモリ: 141,728 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-23 08:12:15
• 合計ジャッジ時間: 27,705 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	24 ms; 5,376 KB
testcase_04	AC	2,111 ms; 5,376 KB
testcase_05	AC	718 ms; 5,376 KB
testcase_06	AC	834 ms; 5,376 KB
testcase_07	AC	1,087 ms; 5,376 KB
testcase_08	AC	1,439 ms; 5,376 KB
testcase_09	AC	1,941 ms; 5,376 KB
testcase_10	AC	1,923 ms; 5,376 KB
testcase_11	AC	1,998 ms; 5,376 KB
testcase_12	AC	2,047 ms; 5,376 KB
testcase_13	AC	2,063 ms; 5,376 KB
testcase_14	AC	2,013 ms; 5,376 KB
testcase_15	AC	2,082 ms; 5,376 KB
testcase_16	AC	774 ms; 5,376 KB
testcase_17	AC	553 ms; 5,376 KB
testcase_18	AC	246 ms; 5,376 KB
testcase_19	AC	1,295 ms; 5,376 KB

ソースコード

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <numeric>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<int> A;
  vector<int> ans;

  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    A.push_back(a);
  }

  ans.push_back(A[0]);

  for (int i = 1; i <= N - 1; ++i) {
    int min_v = INT_MAX;
    int best_idx = 0;

    for (int j = i; j < N; ++j) {
      int v = A[j];
      int l = lcm(A[i - 1], v);

      if (min_v > l) {
        min_v = l;
        best_idx = j;
      } else if (min_v == l && A[best_idx] > A[j]) {
        best_idx = j;
      }
    }

    ans.push_back(A[best_idx]);
    swap(A[i], A[best_idx]);
  }

  for (int i = 0; i < N; ++i) {
    cout << ans[i];
    if (i + 1 < N) cout << " ";
  }
  cout << endl;

  return 0;
}