結果

問題 No.2114 01 Matching
ユーザー gew1fw
提出日時 2025-06-12 18:53:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,885 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 137,456 KB
最終ジャッジ日時 2025-06-12 18:53:23
合計ジャッジ時間 8,784 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, M, K = map(int, sys.stdin.readline().split())
    B = list(map(int, sys.stdin.readline().split()))
    R = list(map(int, sys.stdin.readline().split()))
    
    # Determine A and B (A is the smaller group)
    swap = False
    if N > M:
        A_nodes = R
        B_nodes = B
        A_size = M
        B_size = N
        swap = True
    else:
        A_nodes = B
        B_nodes = R
        A_size = N
        B_size = M
    k = min(N, M)
    
    # Sort A and B
    A_nodes.sort()
    B_nodes.sort()
    
    # Compute mod K arrays
    A_mod = [x % K for x in A_nodes]
    B_mod = [x % K for x in B_nodes]
    
    # Compute rolling hash for A's mod array
    base = 10**18 + 3
    mod = 10**18 + 7
    
    # Precompute powers of base
    max_len = max(len(A_mod), len(B_mod))
    pow_base = [1] * (max_len + 1)
    for i in range(1, max_len + 1):
        pow_base[i] = (pow_base[i-1] * base) % mod
    
    # Compute hash for A's mod array
    a_hash = 0
    for num in A_mod:
        a_hash = (a_hash * base + num) % mod
    
    # Compute rolling hash for B's mod array
    b_hashes = []
    current_hash = 0
    for i in range(len(B_mod)):
        current_hash = (current_hash * base + B_mod[i]) % mod
        b_hashes.append(current_hash)
        if i >= k:
            # Subtract the contribution from the element out of the window
            remove_hash = (B_mod[i - k] * pow_base[k]) % mod
            current_hash = (current_hash - remove_hash) % mod
    
    # Find all i_start where the hash matches
    candidates = []
    for i_start in range(B_size - k + 1):
        if i_start == 0:
            bh = b_hashes[i_start + k - 1]
        else:
            # Compute the hash using rolling hash formula
            bh = (b_hashes[i_start + k - 1] - (b_hashes[i_start - 1] * pow_base[k]) % mod) % mod
        if bh == a_hash:
            candidates.append(i_start)
    
    # Check each candidate for actual mod equality
    valid_candidates = []
    for i_start in candidates:
        valid = True
        for i in range(k):
            if A_mod[i] != B_mod[i_start + i]:
                valid = False
                break
        if valid:
            valid_candidates.append(i_start)
    
    if not valid_candidates:
        print(-1)
        return
    
    # Calculate the minimal cost for valid candidates
    min_cost = float('inf')
    for i_start in valid_candidates:
        total = 0
        for i in range(k):
            a_val = A_nodes[i]
            b_val = B_nodes[i_start + i]
            diff = abs(a_val - b_val)
            if diff % K != 0:
                total = float('inf')
                break
            total += diff // K
        if total < min_cost:
            min_cost = total
    
    if min_cost == float('inf'):
        print(-1)
    else:
        print(min_cost)

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