結果

問題 No.14 最小公倍数ソート
ユーザー firiexpfiriexp
提出日時 2020-04-11 14:21:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,574 bytes
コンパイル時間 666 ms
コンパイル使用メモリ 89,044 KB
最終ジャッジ日時 2024-11-14 22:18:09
合計ジャッジ時間 1,264 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:27:35: error: variable 'std::array<std::array<int, 1000>, 1000> dp' has initializer but incomplete type
   27 |     array<array<int, 1000>, 1000> dp{};
      |                                   ^~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
#include <limits>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;


int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    array<array<int, 1000>, 1000> dp{};
    for (int i = 0; i < 1000; ++i) {
        fill(dp[i].begin(),dp[i].end(), -1);
    }
    auto rec = [&](int a, int b, auto &&f) -> int {
        if(~dp[a][b]) return dp[a][b];
        if(a == 0) return dp[a][b] = b;
        else return dp[a][b] = f(b%a, a, f);
    };
    for (int i = 0; i < 1000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            rec(i, j, rec);
        }
    }
    auto f = [&](int a, int b, auto &&f) -> int {
        if(max(a, b) < 1000) return dp[a][b];
        if(a == 0) return b;
        else return f(b%a, a, f);
    };
    using P = pair<int, int>;
    for (int i = 1; i < n; ++i) {
        P val = {INF<int>, INF<int>}; int cur = i;
        for (int j = i; j < n; ++j) {
            P x = {v[j]*v[i-1]/f(v[i-1], v[j], f), v[j]};
            if(val > x){
                val = x;
                cur = j;
            }
        }
        swap(v[i], v[cur]);
    }

    for (int i = 0; i < n; ++i) {
        if(i) printf(" ");
        printf("%d", v[i]);
    }
    puts("");
    return 0;
}
0