結果
問題 |
No.1055 牛歩
|
ユーザー |
![]() |
提出日時 | 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()