結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー tenten
提出日時 2021-01-27 14:47:45
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,271 bytes
コンパイル時間 2,465 ms
コンパイル使用メモリ 80,372 KB
実行使用メモリ 58,340 KB
最終ジャッジ日時 2024-06-24 16:02:31
合計ジャッジ時間 10,035 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        ArrayList<HashMap<Integer, Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            list.add(getHashMap(arr[i]));
        }
        for (int i = 0; i < n - 2; i++) {
            HashMap<Integer, Integer> target = list.get(i);
            int min = Integer.MAX_VALUE;
            int minIdx = 0;
            for (int j = i + 1; j < n; j++) {
                HashMap<Integer, Integer> current = list.get(j);
                int sum = 1;
                for (int x : current.keySet()) {
                    sum *= getInt(x, current.get(x), target.getOrDefault(x, 0));
                }
                if ((min == sum && arr[minIdx] > arr[j]) || min > sum) {
                    min = sum;
                    minIdx = j;
                }
            }
            int tmp = arr[i + 1];
            arr[i + 1] = arr[minIdx];
            arr[minIdx] = tmp;
            HashMap<Integer, Integer> tMap = list.get(i + 1);
            list.set(i + 1, list.get(minIdx));
            list.set(minIdx, tMap);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                sb.append(" ");
            }
            sb.append(arr[i]);
        }
        System.out.println(sb);
    }
    
    static int getInt(int base, int left, int right) {
        return pow(base, Math.max(0, left - right));
    }
    
    static int pow(int x, int p) {
        if (p == 0) {
            return 1;
        } else if (p % 2 == 0) {
            return pow(x * x, p / 2);
        } else {
            return pow(x, p - 1) * x;
        }
    }
    
    static HashMap<Integer, Integer> getHashMap(int x) {
        HashMap<Integer, Integer> ans = new HashMap<>();
        for (int i = 2; i <= Math.sqrt(x); i++) {
            while (x % i == 0) {
                ans.put(i, ans.getOrDefault(i, 0) + 1);
                x /= i;
            }
        }
        if (x > 0) {
            ans.put(x, ans.getOrDefault(x, 0) + 1);
        }
        return ans;
    }
}
0