結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:45 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 9,958 bytes |
| コンパイル時間 | 226 ms |
| コンパイル使用メモリ | 82,380 KB |
| 実行使用メモリ | 821,220 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:15 |
| 合計ジャッジ時間 | 11,597 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 MLE * 1 -- * 22 |
ソースコード
import sys
# Set a high recursion depth limit for potentially deep searches (large N)
# The problem constraints suggest N could be up to 65535.
# A typical Python default recursion depth is 1000, which is insufficient.
# We need to increase it significantly. 70000 should be safe for N up to 65535.
try:
# Set recursion depth to handle N up to ~70000. Actual required depth depends on N.
sys.setrecursionlimit(70000)
except Exception as e:
# If setting the limit fails (e.g., due to OS restrictions or platform limits),
# print a warning but proceed. The program might crash later with RecursionError.
print(f"Warning: Failed to set recursion depth limit. Error: {e}", file=sys.stderr)
# Memoization dictionary to store results of states (index, used_mask)
# Key: tuple (current index in C, bitmask of used numbers)
# Value: tuple (boolean indicating success, tuple representing permutation suffix if success)
memo = {}
# Input string C
C = ""
# Length of C
C_len = 0
# Estimated upper bound for N. This is used for pruning the search space.
# Numbers larger than N_limit will not be considered.
N_limit = 0
# Maximum length of a binary string segment to consider.
# Determined based on N_limit. A number P_k <= N_limit has at most N_limit.bit_length() bits.
MAX_BIN_LEN = 1 # Initialize, will be updated
def solve():
"""
Main function to read input, estimate parameters, invoke the recursive search,
and print the resulting permutation.
"""
global C, C_len, N_limit, memo, MAX_BIN_LEN
# Read the input string C from standard input
C = sys.stdin.readline().strip()
C_len = len(C)
# Handle edge case: empty input string.
# Based on constraints |C| >= 1, this case might not occur. If it could, decide output.
if C_len == 0:
print() # Output empty line for empty input? Or assume error?
return
# Estimate N roughly to define N_limit for pruning.
# We find the smallest N such that the sum of binary lengths of 1..N is at least |C|.
# This N serves as a lower bound / estimate for the actual N of the permutation.
current_total_len = 0
k = 0 # This k will store the estimated N
temp_N = 0 # Loop variable for estimation
# Iterate N and accumulate total length of binary representations for 1..N
while current_total_len < C_len:
temp_N += 1
# Safety break if N estimate grows excessively large (e.g. > 70000)
# This might indicate an issue with input or extremely large N beyond expectation.
# Max N related to 2^16-1 = 65535 from problem description. 70000 is a safe check bound.
if temp_N > 70000:
print("Error: Estimated N exceeds reasonable limit (70000).", file=sys.stderr)
return # Exit if N seems too large
# k.bit_length() computes floor(log2 k) + 1 efficiently for k >= 1
len_k = temp_N.bit_length()
current_total_len += len_k
# k becomes the first N value where TotalL(N) >= C_len
k = temp_N
# Set N_limit = k + buffer. A small buffer (e.g., 5) accommodates cases where the permutation
# might contain numbers slightly larger than the initial estimate k, potentially due to
# skewness in lengths (more shorter numbers balanced by few very long ones).
N_limit = k + 5
# Ensure N_limit is at least 1 (for edge cases with very short C string)
if N_limit == 0: N_limit = 1
# Update MAX_BIN_LEN based on the determined N_limit.
# The maximum binary length needed is for the number N_limit itself.
if N_limit > 0:
MAX_BIN_LEN = N_limit.bit_length()
else: # If N_limit is 0 (e.g. if C was empty string and logic reached here)
MAX_BIN_LEN = 1 # Minimum length is 1 ('1')
# MAX_BIN_LEN should be at least 1. If N_limit=0 results in bit_length 0, fix it.
if MAX_BIN_LEN == 0: MAX_BIN_LEN = 1
# Clear memoization table for a fresh run for the current test case
memo = {}
# Start the backtracking search from index 0 with an empty mask (no numbers used yet)
found, path_tuple = search(0, 0)
# If a valid permutation path was found
if found:
# Print the permutation elements space-separated
print(*(list(path_tuple)))
else:
# This case should technically not happen based on the problem guarantee
# that a solution exists. If it does, it indicates a potential issue:
# logic error, wrong assumptions, or violation of problem guarantee in test data.
print("Error: Solution not found. Problem guarantee might be violated or logic error.", file=sys.stderr)
def search(index, used_mask):
"""
Recursive search function with memoization to find a valid permutation.
Args:
index: The current starting index in the string C to parse the next number from.
used_mask: A bitmask where the i-th bit is set if the number (i+1) has been used.
Returns:
tuple: (bool, tuple)
- bool: True if a valid permutation suffix was found from this state, False otherwise.
- tuple: The suffix of the permutation path if found, otherwise None.
An empty tuple `()` indicates successful termination at the end of C.
"""
# State tuple used as key for memoization
state = (index, used_mask)
# Return memoized result if this state has been visited before
if state in memo:
return memo[state]
# Base Case: Successfully parsed the entire string C
if index == C_len:
# Check if the sequence of numbers found constitutes a valid permutation {1, ..., N}
# Count the number of elements found (number of set bits in the mask)
num_elements = bin(used_mask).count('1')
# If no elements were found (e.g., empty C was input and somehow reached here), invalid.
if num_elements == 0:
return False, None # Return failure
# Determine N = maximum value present in the permutation.
# N is the index of the most significant bit + 1. int.bit_length() gives this.
max_val = used_mask.bit_length()
# Check Condition 1: The number of elements must equal N (the maximum value).
# This ensures the set is dense from 1 to N without gaps.
if num_elements != max_val:
return False, None # Failure: count mismatch max_val implies gaps or count error
# Check Condition 2: The set of numbers must be exactly {1, ..., N}.
# This check is implicitly covered by Condition 1 IF the mask construction is correct.
# Explicit check: The mask must have bits 0 to N-1 set, which is value (1 << N) - 1.
expected_mask_val = (1 << max_val) - 1
if used_mask == expected_mask_val:
# Valid permutation found! Return success and empty tuple path suffix.
return True, ()
else:
# Failure: Mask doesn't match the expected full set {1..N}.
# This indicates some numbers between 1 and N are missing.
return False, None
# Pruning: If current index has somehow exceeded string length, invalid path.
if index > C_len:
return False, None
# Default result indicating failure for this state (will be updated if success found)
res = (False, None)
# Recursive Step: Explore possible next numbers P_k by trying different lengths L
# Iterate L from 1 up to MAX_BIN_LEN (max possible length of binary string for numbers up to N_limit)
for L in range(1, MAX_BIN_LEN + 1):
# Boundary check: ensure substring C[index : index+L] is within the bounds of C
if index + L > C_len:
break # Cannot form substring of length L, stop trying longer lengths
# Extract substring S_k potentially representing the next number P_k
current_num_str = C[index : index+L]
# Optimization: Binary representation of any positive integer must start with '1'.
# If the substring starts with '0', it cannot be a valid binary representation.
if current_num_str[0] == '0':
continue # Skip this length L, try the next length
# Convert the binary string to an integer P_k
P_k = int(current_num_str, 2)
# Pruning: Check if P_k is within the valid range {1..N_limit}.
# P_k must be positive. Check against N_limit as a heuristic upper bound.
# If P_k > N_limit, it's likely too large for the final permutation N.
if P_k == 0 or P_k > N_limit:
continue # P_k outside reasonable range {1..N_limit}, skip this P_k
# Pruning: Check if P_k has already been used in the current path.
# Check the (P_k - 1)-th bit in used_mask. If it's set, P_k is already used.
if (used_mask >> (P_k - 1)) & 1:
continue # Number P_k already used, cannot reuse. Skip this P_k.
# If P_k is valid (within range, starts with '1') and unused, make a recursive call
# Create the new mask by setting the bit corresponding to P_k
new_mask = used_mask | (1 << (P_k - 1))
# Recursive call for the remainder of the string, starting from new index `index + L`
found, path_suffix_tuple = search(index + L, new_mask)
# If the recursive call found a complete valid solution path
if found:
# Construct the result for the current state: success = True, path = (P_k,) + suffix
res = (True, (P_k,) + path_suffix_tuple)
# Since we only need ONE solution, break the loop immediately after finding one.
break
# Store the computed result (success/failure status + path suffix if success) in memo table
memo[state] = res
return res
# Execute the main solver function when the script is run
solve()