結果

問題 No.2114 01 Matching
ユーザー lam6er
提出日時 2025-04-16 00:31:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,962 bytes
コンパイル時間 730 ms
コンパイル使用メモリ 81,152 KB
実行使用メモリ 180,272 KB
最終ジャッジ日時 2025-04-16 00:33:36
合計ジャッジ時間 28,138 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    B = list(map(int, data[idx:idx+N]))
    idx += N
    R = list(map(int, data[idx:idx+M]))
    idx += M

    from collections import defaultdict
    mod_blue = defaultdict(list)
    mod_red = defaultdict(list)

    for b in B:
        mod = b % K
        mod_blue[mod].append(b)
    for r in R:
        mod = r % K
        mod_red[mod].append(r)

    S = min(N, M)
    total = 0
    cost_list = []

    for mod in mod_blue:
        if mod not in mod_red:
            continue
        blue = sorted(mod_blue[mod])
        red = sorted(mod_red[mod])
        len_b = len(blue)
        len_r = len(red)
        s_g = min(len_b, len_r)
        if s_g == 0:
            continue
        total += s_g

        # For each red element, find the closest in blue and compute the minimal diff
        red_diff = []
        for r_val in red:
            pos = bisect.bisect_left(blue, r_val)
            min_diff = float('inf')
            if pos < len_b:
                min_diff = min(min_diff, abs(blue[pos] - r_val))
            if pos > 0:
                min_diff = min(min_diff, abs(blue[pos-1] - r_val))
            red_diff.append( (min_diff, r_val) )

        # Sort red by the minimal diff, then take top s_g elements
        red_diff.sort()
        selected_red = [rd[1] for rd in red_diff[:s_g]]
        selected_red.sort()

        # Pair blue and selected_red
        current_cost = []
        for b_val, r_val in zip(blue[:s_g], selected_red):
            delta = abs(b_val - r_val)
            cost = delta // K
            current_cost.append(cost)
        cost_list.extend(current_cost)

    if len(cost_list) < S:
        print(-1)
        return

    cost_list.sort()
    print(sum(cost_list[:S]))

if __name__ == '__main__':
    main()
0