結果

問題 No.2114 01 Matching
ユーザー gew1fw
提出日時 2025-06-12 13:51:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,502 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 139,612 KB
最終ジャッジ日時 2025-06-12 13:52:37
合計ジャッジ時間 10,617 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    # Check if all B and R have the same mod K
    if N == 0 or M == 0:
        print(-1)
        return
    mod_b = B[0] % K
    for b in B:
        if b % K != mod_b:
            print(-1)
            return
    mod_r = R[0] % K
    for r in R:
        if r % K != mod_r:
            print(-1)
            return
    if mod_b != mod_r:
        print(-1)
        return

    # Convert to x and y
    r_mod = mod_b
    x = [(b - r_mod) // K for b in B]
    y = [(r - r_mod) // K for r in R]
    x.sort()
    y.sort()

    def find_min_cost(a, a_size, b, b_size):
        if a_size == 0 or b_size == 0:
            return 0 if a_size == 0 and b_size == 0 else -1
        # a is the smaller list, we need to choose a_size elements from b
        candidates = set()
        # Use median of a to find potential k
        m = a_size // 2
        a_median = a[m]
        # Find closest in b
        low = 0
        high = b_size
        while low < high:
            mid = (low + high) // 2
            if b[mid] < a_median:
                low = mid + 1
            else:
                high = mid
        best_p = low
        if best_p < b_size:
            if best_p > 0 and abs(b[best_p - 1] - a_median) < abs(b[best_p] - a_median):
                best_p -= 1
        else:
            best_p = b_size - 1
        k_candidate = best_p - m
        # Generate candidate k around k_candidate
        for dk in range(-2, 3):
            candidates.add(k_candidate + dk)
        # Also check the start and end
        candidates.add(0)
        candidates.add(b_size - a_size)
        min_cost = float('inf')
        for k in candidates:
            if k < 0 or k + a_size > b_size:
                continue
            current_cost = 0
            for i in range(a_size):
                current_cost += abs(a[i] - b[k + i])
                if current_cost >= min_cost:
                    break
            if current_cost < min_cost:
                min_cost = current_cost
        return min_cost if min_cost != float('inf') else -1

    if N <= M:
        cost = find_min_cost(x, N, y, M)
    else:
        cost = find_min_cost(y, M, x, N)
    print(cost if cost != -1 else -1)

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