結果

問題 No.2114 01 Matching
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:57:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,389 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 180,392 KB
最終ジャッジ日時 2025-04-09 20:59:28
合計ジャッジ時間 14,817 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)

    total_pairs = 0
    possible = True
    for mod in mod_blue:
        if mod not in mod_red:
            continue
        bc = len(mod_blue[mod])
        rc = len(mod_red[mod])
        total_pairs += min(bc, rc)
    req = min(N, M)
    if total_pairs < req:
        print(-1)
        return

    cost = 0
    for mod in mod_blue:
        if mod not in mod_red:
            continue
        blues = sorted(mod_blue[mod])
        reds = sorted(mod_red[mod])
        nb = len(blues)
        nr = len(reds)
        pairs_needed = min(nb, nr)
        j = 0
        for b in blues:
            if j >= nr:
                break
            idx_r = bisect.bisect_left(reds, b, lo=j)
            best_diff = None
            best_pos = -1
            if idx_r > j:
                pos = idx_r -1
                diff = b - reds[pos]
                best_diff = diff
                best_pos = pos
            if idx_r < nr:
                diff = reds[idx_r] - b
                if best_diff is None or diff < best_diff:
                    best_diff = diff
                    best_pos = idx_r
            if best_pos == -1:
                continue
            current_red = reds[best_pos]
            max_val = max(b, current_red)
            a = (max_val - b) // K
            a_r = (max_val - current_red) // K
            cost += a + a_r
            j = best_pos + 1
            pairs_needed -= 1
            if pairs_needed == 0:
                break
        while pairs_needed >0:
            best_pos = len(reds) -1
            current_red = reds[best_pos]
            b = blues[-pairs_needed]
            max_val = max(b, current_red)
            a = (max_val - b) // K
            a_r = (max_val - current_red) // K
            cost += a + a_r
            pairs_needed -=1
    print(cost)

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