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

• 問題: No.14 最小公倍数ソート
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:17:16
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 4,531 ms / 5,000 ms
• コード長: 6,417 bytes
• コンパイル時間: 850 ms
• コンパイル使用メモリ: 83,948 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:19:36
• 合計ジャッジ時間: 51,424 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 20

ソースコード

#include <iostream> // For input/output operations (cin, cout)
#include <vector>   // For using std::vector dynamic array
#include <numeric>  // Required for std::gcd (available in C++17 standard library)
#include <algorithm> // Required for std::sort and std::swap
#include <utility>  // Required for std::pair

// Define a custom gcd function if not using C++17 or later.
// The #if directive checks the version of the C++ standard being used.
#if __cplusplus < 201703L
// Implementation of the Euclidean algorithm for GCD
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    // GCD is the value of 'a' when 'b' becomes 0
    return a;
}
// Define std::gcd equivalent for older standards to maintain compatibility
namespace std {
    // Wrapper function that calls the custom gcd implementation
    long long gcd(long long a, long long b) {
        return ::gcd(a, b); // Use the globally defined gcd function
    }
}
#endif

// Custom comparator structure for sorting pairs of {sort_key, original_value}
// The sort key is derived from the LCM calculation, specifically f_k(a_i) = a_i / gcd(a_k, a_i)
struct PairComparator {
     // Overload the function call operator '()' to define the comparison logic
     bool operator()(const std::pair<long long, long long>& p1, const std::pair<long long, long long>& p2) const {
        // p1 represents the pair {f_k(a_i), a_i}
        // p2 represents the pair {f_k(a_j), a_j}
        
        if (p1.first != p2.first) {
            // If the primary sort keys (f_k values) are different, sort based on these keys.
            // Return true if p1's key is less than p2's key, meaning p1 comes first.
            return p1.first < p2.first; 
        } else {
            // If the primary sort keys are equal, use the original values (a_i, a_j) as a tie-breaker.
            // Return true if p1's original value is less than p2's original value.
            return p1.second < p2.second; 
        }
    }
};

int main() {
    // Optimize C++ standard streams I/O for potentially faster execution, especially with large inputs.
    std::ios_base::sync_with_stdio(false); // Disable synchronization with C stdio
    std::cin.tie(NULL); // Untie cin from cout

    int N; // Declare variable to store the number of integers
    std::cin >> N; // Read the number of integers from standard input

    // Declare a vector 'a' of type long long to store the N integers.
    // Using long long provides safety against potential arithmetic overflows.
    std::vector<long long> a(N); 
    for (int i = 0; i < N; ++i) {
        std::cin >> a[i]; // Read each integer into the vector
    }

    // Declare a temporary vector 'temp_pairs' to store pairs for sorting in each step.
    // Each pair will contain {sort_key, original_value}.
    std::vector<std::pair<long long, long long>> temp_pairs;

    // The main loop iterates from k = 0 to N-2 (total N-1 steps).
    // In step k, elements a[0]...a[k] remain fixed in their positions.
    // The subarray a[k+1]...a[N-1] is sorted based on the element a[k].
    for (int k = 0; k < N - 1; ++k) {
        long long fixed_ak = a[k]; // The element a[k] used as the reference for LCM comparisons.
        
        // Clear the temporary vector to reuse it for the current step's sort operation.
        temp_pairs.clear();
        
        // Calculate the number of elements in the subarray that needs to be sorted.
        int sub_array_size = N - (k + 1);

        // Proceed with sorting only if the subarray is non-empty (has elements).
        if (sub_array_size > 0) {
             // Reserve memory capacity in the vector equal to the subarray size.
             // This can improve performance by avoiding dynamic memory reallocations during push_back operations.
             temp_pairs.reserve(sub_array_size);

             // Iterate through the elements a[i] of the subarray (from index k+1 to N-1).
             // Compute the sort key f_k(a_i) for each element and store the pair {f_k(a_i), a[i]}.
             for (int i = k + 1; i < N; ++i) {
                long long current_ai = a[i]; // The current element being processed.
                // Calculate the greatest common divisor (GCD) of the fixed element a[k] and the current element a[i].
                // Use std::gcd if available (C++17), otherwise the custom implementation.
                long long common_divisor = std::gcd(fixed_ak, current_ai);
                
                // Calculate the primary sort key f_k(a_i) = a_i / gcd(a_k, a_i).
                // Since input values a_i are >= 1, the fixed element a_k will also be >= 1 after the first element.
                // Thus, gcd(fixed_ak, current_ai) will always be >= 1, making the division safe.
                long long f_k_ai = current_ai / common_divisor; 
                
                // Add the computed pair {sort_key, original_value} to the temporary vector.
                temp_pairs.push_back({f_k_ai, current_ai});
            }
            
            // Sort the vector of pairs using std::sort.
            // The custom comparator 'PairComparator' defines the sorting rules (primary key f_k, secondary key original value).
            // std::sort typically has an average time complexity of O(M log M), where M is the number of elements.
            std::sort(temp_pairs.begin(), temp_pairs.end(), PairComparator());

            // After sorting the pairs, update the original array 'a' in place.
            // The elements in the subarray a[k+1]...a[N-1] are replaced by the sorted sequence.
            // The sorted sequence consists of the original values (second component of the pairs) in their new order.
            for (int i = 0; i < temp_pairs.size(); ++i) {
                // Place the i-th element of the sorted sequence into a[k+1+i].
                a[k + 1 + i] = temp_pairs[i].second;
            }
        }
    }

    // After completing all N-1 steps, output the final state of the array 'a'.
    for (int i = 0; i < N; ++i) {
        // Print each element followed by a space, but avoid a trailing space after the last element.
        std::cout << a[i] << (i == N - 1 ? "" : " ");
    }
    // Print a newline character at the end of the output line.
    std::cout << std::endl;

    return 0; // Return 0 to indicate successful program execution.
}