結果

問題 No.1055 牛歩
ユーザー gew1fw
提出日時 2025-06-12 14:04:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,448 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 152,832 KB
最終ジャッジ日時 2025-06-12 14:04:59
合計ジャッジ時間 14,889 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 53 WA * 16 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0

    N = int(data[ptr])
    ptr +=1
    M = int(data[ptr])
    ptr +=1

    A = list(map(int, data[ptr:ptr+M]))
    ptr += M

    # Initialize pos array (1-based)
    pos = [0]*(M+1)
    for i in range(1, M+1):
        pos[i] = A[i-1]

    # Initialize sorted_positions and positions set
    sorted_positions = A.copy()
    sorted_positions.sort()
    positions = set(A)

    Q = int(data[ptr])
    ptr +=1
    B = list(map(int, data[ptr:ptr+Q]))

    for b in B:
        current_pos = pos[b]

        possible_moves = []
        # Check left
        new_pos = current_pos -1
        if new_pos >=1 and new_pos not in positions:
            possible_moves.append(new_pos)
        # Check right
        new_pos = current_pos +1
        if new_pos <= N and new_pos not in positions:
            possible_moves.append(new_pos)

        if not possible_moves:
            print("NO")
            return

        # For each possible move, compute available space
        max_total = -1
        best_new_pos = possible_moves[0]
        max_available_left = -1

        for new_pos in possible_moves:
            # Find the number of pieces left and right
            idx_left = bisect.bisect_left(sorted_positions, new_pos)
            left_count = idx_left

            idx_right = bisect.bisect_right(sorted_positions, new_pos)
            right_count = len(sorted_positions) - idx_right

            available_left = new_pos -1 - left_count
            available_right = N - new_pos - right_count
            total = available_left + available_right

            if total > max_total or (total == max_total and available_left > max_available_left):
                max_total = total
                max_available_left = available_left
                best_new_pos = new_pos

        # Update data structures
        # Remove current_pos from sorted_positions
        idx = bisect.bisect_left(sorted_positions, current_pos)
        if idx < len(sorted_positions) and sorted_positions[idx] == current_pos:
            sorted_positions.pop(idx)
        # Add best_new_pos to sorted_positions
        bisect.insort(sorted_positions, best_new_pos)

        # Update the set and pos array
        positions.remove(current_pos)
        positions.add(best_new_pos)
        pos[b] = best_new_pos

    print("YES")

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