結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー id-ord
提出日時 2026-01-14 09:47:03
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,472 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,293 ms
コンパイル使用メモリ 192,484 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2026-01-14 09:47:08
合計ジャッジ時間 4,921 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
次のファイルから読み込み:  /usr/local/gcc-15/include/c++/15.2.0/bits/stl_iterator.h:78,
         次から読み込み:  /usr/local/gcc-15/include/c++/15.2.0/bits/stl_algobase.h:67,
         次から読み込み:  /usr/local/gcc-15/include/c++/15.2.0/algorithm:62,
         次から読み込み:  main.cpp:2:
In function ‘constexpr _Tp* std::construct_at(_Tp*, _Args&& ...) [with _Tp = int; _Args = {const int&}]’,
    inlined from ‘static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = int]’ at /usr/local/gcc-15/include/c++/15.2.0/bits/alloc_traits.h:676:21,
    inlined from ‘constexpr void std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::_M_realloc_append(_Args&& ...) [with _Args = {const int&}; _Tp = int; _Alloc = std::allocator<int>]’ at /usr/local/gcc-15/include/c++/15.2.0/bits/vector.tcc:586:26,
    inlined from ‘constexpr void std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>]’ at /usr/local/gcc-15/include/c++/15.2.0/bits/stl_vector.h:1427:21,
    inlined from ‘int main()’ at main.cpp:42:18:
/usr/local/gcc-15/include/c++/15.2.0/bits/stl_construct.h:110:16: 警告: ‘min_an’ may be used uninitialized [-Wmaybe-uninitialized]
  110 |         return ::new(__loc) _Tp(std::forward<_Args>(__args)...);
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:24:22: 備考: ‘min_an’ はここで定義されています
   24 |     int min = 10001, min_an;
      |                      ^~~~~~

ソースコード

diff #
raw source code 

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

int main() {
  std::map<int, std::multiset<int>> d;  // d[n]=ak@(ak%(n)==0)
  int N;
  std::cin >> N;
  std::vector<int> ans, a(N);
  for (auto& i : a) std::cin >> i;
  std::sort(a.begin() + 1, a.end());
  for (int i = 1; i < N; i++) {
    for (int j = 1; j * j <= a[i]; j++)
      if (a[i] % j == 0) {
        if (j * j != a[i]) d[a[i] / j].insert(a[i]);
        d[j].insert(a[i]);
      }
  }
  ans.push_back(a[0]);
  while (ans.size() < N) {
    int min = 10001, min_an;
    for (int j = 1; j * j <= ans.back(); j++)
      if (ans.back() % j == 0) {
        if (d.contains(j)) {
          int an = *(d[j].begin());
          if (min > an / j) {
            min = an / j;
            min_an = an;
          }
        }
        if (d.contains(ans.back() / j)) {
          int an = *(d[ans.back() / j].begin());
          if (min > an / (ans.back() / j)) {
            min = an / (ans.back() / j);
            min_an = an;
          }
        }
      }
    ans.push_back(min_an);
    for (int j = 1; j * j <= min_an; j++)
      if (min_an % j == 0) {
        if (j * j != min_an) {
          d[min_an / j].erase(d[min_an / j].find(min_an));
          if (d[min_an / j].empty()) d.erase(min_an / j);
        }
        d[j].erase(d[j].find(min_an));
        if (d[j].empty()) d.erase(j);
      }
  }
  for (auto n : ans) std::cout << n << " ";
  std::cout << std::endl;
  return 0;
}
0