結果

問題 No.2114 01 Matching
ユーザー qwewe
提出日時 2025-05-14 13:03:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,130 bytes
コンパイル時間 1,270 ms
コンパイル使用メモリ 112,284 KB
実行使用メモリ 50,176 KB
最終ジャッジ日時 2025-05-14 13:04:47
合計ジャッジ時間 15,574 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 3 TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
#include <set> // Use multiset for implementation (though not used in final slow version)
#include <cmath> // For std::abs

// Function to calculate the minimum cost for a specific remainder group.
// Uses a slow O(N_r * (M_r - N_r + 1)) approach which might TLE on large cases,
// but is logically correct based on the derived cost function and matching property.
// N_r = |B|, M_r = |R|. Assumes N_r <= M_r after potential swap.
long long calculate_min_cost_for_remainder_slow(std::vector<long long>& B, std::vector<long long>& R, long long K) {
    int N = B.size();
    int M = R.size();

    // If either group is empty, no matching is possible, cost is 0.
    if (N == 0 || M == 0) {
        return 0;
    }

    // Ensure N <= M by swapping if necessary.
    // The property requires matching all vertices of the smaller set.
    if (N > M) {
        std::swap(B, R);
        std::swap(N, M);
    }
    
    // Sort both lists to apply the property that optimal matching pairs B_i with R_{k+i-1}.
    // Since using 0-based indexing, match B[i] with R[k+i].
    std::sort(B.begin(), B.end());
    std::sort(R.begin(), R.end());

    // Initialize minimum total absolute difference sum with -1 (or a very large value).
    // This variable will store minimum of Sum |B[i] - R[k+i]| over all possible k.
    long long min_total_abs_diff = -1; 

    // Iterate through all possible start indices k for the subarray in R.
    // k ranges from 0 to M - N.
    for (int k = 0; k <= M - N; ++k) {
         long long current_sum_abs_diff = 0;
         // Calculate the sum of absolute differences for the current window k.
         // Matches B[i] with R[k+i] for i = 0 to N-1.
         for (int i = 0; i < N; ++i) {
              current_sum_abs_diff += std::abs(B[i] - R[k + i]);
         }
         // Update the minimum sum found so far.
         if (min_total_abs_diff == -1 || current_sum_abs_diff < min_total_abs_diff) {
              min_total_abs_diff = current_sum_abs_diff;
         }
    }

    // If N=0 originally, this function returns 0 early.
    // If N > 0, then M >= N > 0, so M-N >= 0, loop runs at least once.
    // min_total_abs_diff will hold a non-negative value.
    
    // The cost is the sum of operations, which is sum of |B_i - R_j| / K.
    return min_total_abs_diff / K;
}


int main() {
    // Faster I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N, M; // Number of blue and red vertices
    long long K; // Value to increase by
    std::cin >> N >> M >> K;

    // Read initial values for blue vertices
    std::vector<long long> B_orig(N);
    for (int i = 0; i < N; ++i) std::cin >> B_orig[i];
    // Read initial values for red vertices
    std::vector<long long> R_orig(M);
    for (int i = 0; i < M; ++i) std::cin >> R_orig[i];

    // Group vertices by their value modulo K
    std::map<long long, std::vector<long long>> B_groups;
    for (int i = 0; i < N; ++i) {
        B_groups[B_orig[i] % K].push_back(B_orig[i]);
    }

    std::map<long long, std::vector<long long>> R_groups;
    for (int i = 0; i < M; ++i) {
        R_groups[R_orig[i] % K].push_back(R_orig[i]);
    }

    // Calculate the maximum possible number of edges that can be formed.
    // This is the sum of minimum sizes of corresponding remainder groups.
    long long max_possible_edges = 0;
    std::vector<long long> remainders; // Store remainders that have vertices on both sides
    for (auto const& [rem, b_list] : B_groups) {
        // Check if this remainder group also exists for red vertices
        if (R_groups.count(rem)) {
             // Add the maximum possible matches for this remainder group
             max_possible_edges += std::min((long long)b_list.size(), (long long)R_groups[rem].size());
             // Store this remainder for later processing
             remainders.push_back(rem);
        }
    }
    
    // Check if the target number of edges (min(N, M)) is achievable.
    // Maximum possible edges must be at least min(N, M).
    // We derived earlier that max_possible_edges <= min(N, M).
    // So achievability requires max_possible_edges == min(N, M).
    if (max_possible_edges < std::min(N, M)) {
        std::cout << -1 << std::endl;
        return 0;
    }

    // If achievable, calculate the total minimum cost.
    long long total_min_cost = 0;
    // Iterate through only those remainders that have vertices in both B and R groups.
    for (long long rem : remainders) {
          std::vector<long long> B_rem = B_groups[rem];
          std::vector<long long> R_rem = R_groups[rem];
          // Calculate the minimum cost for this remainder group and add to total.
          // Using the slow O(N*M) function temporarily. For competitive programming,
          // a faster O(M log N) or O(M log M) approach would be needed for large inputs.
          total_min_cost += calculate_min_cost_for_remainder_slow(B_rem, R_rem, K);
     }
    
    // Output the total minimum cost.
    std::cout << total_min_cost << std::endl;

    return 0;
}
0