結果

問題 No.3754 Mischievous Resident (Hard)
コンテスト
ユーザー marc2825
提出日時 2026-09-12 15:42:26
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,627 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 63 ms
コンパイル使用メモリ 82,872 KB
実行使用メモリ 161,516 KB
最終ジャッジ日時 2026-10-02 21:06:49
合計ジャッジ時間 19,109 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    it = iter(input_data)
    num_test_cases = int(next(it))
    output = []

    for _ in range(num_test_cases):
        building_floors = int(next(it))
        num_elevators = int(next(it))

        start_floors = [int(next(it)) for _ in range(num_elevators)]
        goal_floors = [int(next(it)) for _ in range(num_elevators)]

        # 各エレベーターの (初期位置, 目的位置) をソート
        elevators = sorted(zip(start_floors, goal_floors))

        possible = True
        for i in range(num_elevators - 1):
            s1, g1 = elevators[i]
            s2, g2 = elevators[i + 1]

            # 順序が逆転している場合は到達不可能
            if g1 > g2:
                possible = False
                break
            # 同じ階に到達する場合、最初からその階に揃っていなければ合流不可能
            if g1 == g2:
                if not (s1 == g1 and s2 == g2):
                    possible = False
                    break

        if not possible:
            output.append("-1")
            continue

        total_operations = 0
        for i in range(num_elevators):
            curr_s, curr_g = elevators[i]

            if curr_s == curr_g:
                continue

            if curr_s < curr_g:
                # 右へ移動
                if i == num_elevators - 1:
                    total_operations += 1
                else:
                    next_s, next_g = elevators[i + 1]
                    right_bound = max(next_s, next_g)
                    d0 = right_bound - curr_s
                    d_target = right_bound - curr_g

                    k = 1
                    val = d_target * 2
                    while val < d0:
                        val *= 2
                        k += 1
                    total_operations += k

            else:
                # 左へ移動
                if i == 0:
                    total_operations += 1
                else:
                    prev_s, prev_g = elevators[i - 1]
                    left_bound = min(prev_s, prev_g)
                    d0 = curr_s - left_bound
                    d_target = curr_g - left_bound

                    k = 1
                    val = d_target * 2
                    while val < d0:
                        val *= 2
                        k += 1
                    total_operations += k

        output.append(str(total_operations))

    sys.stdout.write("\n".join(output) + "\n")


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