結果
| 問題 |
No.1055 牛歩
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:07 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,858 bytes |
| コンパイル時間 | 188 ms |
| コンパイル使用メモリ | 82,212 KB |
| 実行使用メモリ | 709,592 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:36 |
| 合計ジャッジ時間 | 5,162 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 5 |
| other | MLE * 1 -- * 69 |
ソースコード
import sys
def solve():
# Read N (number of squares) and M (number of pieces)
N, M = map(int, sys.stdin.readline().split())
# Read initial positions A_1, ..., A_M
# The input guarantees A are sorted and distinct: 1 <= A_1 < A_2 < ... < A_M <= N
A = list(map(int, sys.stdin.readline().split()))
# Read Q (number of instructions)
# Use readline().strip() to handle potential empty line or extra whitespace. Check if it's empty.
q_line = sys.stdin.readline().strip()
if not q_line:
Q = 0
else:
try:
Q = int(q_line)
except ValueError:
# Handle case where Q line might be invalid, though problem statement implies valid integer input
# Based on constraints, Q >= 1 if B is provided. If Q=0, B won't be provided.
# Let's assume valid input per problem statement structure. Minimal Q is likely 1 if B list exists.
# The provided sample inputs always have Q >= 1 with a B list.
# For safety against weird inputs, let's default to 0 if conversion fails and B is empty.
# If B has content, Q must be > 0. Let's rely on input format guarantee.
Q = int(q_line)
# If Q is 0, no moves are required, so it's always possible.
if Q == 0:
print("YES")
return
# Read the sequence of piece indices B_1, ..., B_Q to be moved
B = list(map(int, sys.stdin.readline().split()))
# Set to store reachable states. A state is represented as a tuple of piece positions (p_1, ..., p_M).
# Using a tuple makes the state hashable and usable in a set.
# Initialize the set with the starting state.
current_states = {tuple(A)}
# Process each instruction B_k from k=0 to Q-1
for k in range(Q):
# Get the index of the piece to move (1-based index as per problem statement)
piece_idx_1based = B[k]
# Convert to 0-based index for list access (Python lists are 0-indexed)
piece_idx_0based = piece_idx_1based - 1
# Set to store states reachable after this k-th move
next_states = set()
# If there are no current states reachable, it's impossible to continue.
# This condition means from all states reachable before step k, none allow a valid move for piece B[k].
if not current_states:
print("NO")
return
# Iterate through all currently reachable states
for state in current_states:
# Convert the tuple state back to a list to potentially modify positions.
# `p` will hold the positions [p_1, ..., p_M] for the current state `state`.
p = list(state)
current_pos = p[piece_idx_0based] # Position of the piece to be moved
# --- Check left move possibility ---
# Calculate the target position if moved left
target_pos_L = current_pos - 1
# Check boundary condition: target position must be at least 1.
if target_pos_L >= 1:
# Collision check:
# If it's the first piece (piece 1, index 0), there's no piece to its left. Only boundary check matters.
# If it's not the first piece, check if moving left would collide with its left neighbor (piece piece_idx_1based - 1).
# The left neighbor is at index piece_idx_0based - 1.
# The new position target_pos_L must be strictly greater than the left neighbor's position p[piece_idx_0based - 1]
# to maintain the relative order p_1 < p_2 < ... < p_M.
# This uses Python's short-circuit evaluation: if piece_idx_1based == 1, the second condition is not checked.
if piece_idx_1based == 1 or target_pos_L > p[piece_idx_0based - 1]:
# If the move is valid (within bounds and no collision), calculate the new state.
# Create a copy of the current positions list
new_p_L = list(p)
# Update the position of the moved piece
new_p_L[piece_idx_0based] = target_pos_L
# Add the resulting state (as a tuple) to the set of next possible states.
next_states.add(tuple(new_p_L))
# --- Check right move possibility ---
# Calculate the target position if moved right
target_pos_R = current_pos + 1
# Check boundary condition: target position must be at most N.
if target_pos_R <= N:
# Collision check:
# If it's the last piece (piece M, index M-1), there's no piece to its right. Only boundary check matters.
# If it's not the last piece, check if moving right would collide with its right neighbor (piece piece_idx_1based + 1).
# The right neighbor is at index piece_idx_0based + 1.
# The new position target_pos_R must be strictly less than the right neighbor's position p[piece_idx_0based + 1].
# Uses short-circuit evaluation: if piece_idx_1based == M, the second condition is not checked.
if piece_idx_1based == M or target_pos_R < p[piece_idx_0based + 1]:
# If the move is valid, calculate the new state.
# Create a copy of the current positions list
new_p_R = list(p)
# Update the position of the moved piece
new_p_R[piece_idx_0based] = target_pos_R
# Add the resulting state (as a tuple) to the set of next possible states.
next_states.add(tuple(new_p_R))
# After checking all possible moves from all current states, update the set of current states for the next iteration.
current_states = next_states
# If after processing moves for step k, the set of next_states is empty,
# it means no valid move could be made for piece B[k] from any state reachable at step k-1.
# Therefore, it's impossible to follow the instructions. Print NO and exit.
# This check is implicitly handled by the 'if not current_states:' check at the beginning of the next loop iteration.
# Adding an explicit check here is also fine.
if not current_states:
print("NO")
return
# If the loop completes successfully for all Q instructions:
# It means that for every instruction k, there was at least one state reachable at step k-1
# from which piece B[k] could make a valid move.
# And after the Q-th instruction, the set current_states is non-empty.
# Therefore, it is possible to follow all instructions.
print("YES")
# Call the solve function to execute the logic
solve()