結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,043 bytes |
| コンパイル時間 | 484 ms |
| コンパイル使用メモリ | 82,148 KB |
| 実行使用メモリ | 111,392 KB |
| 最終ジャッジ日時 | 2025-05-14 13:22:30 |
| 合計ジャッジ時間 | 11,205 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 TLE * 1 -- * 22 |
ソースコード
import sys
# Global variables for the recursive solver
C_STR_G = ""
N_G = 0
MAX_BITS_N_G = 0 # Max number of bits for any number up to N_G
RESULT_PERMUTATION_G = [] # Stores the permutation being built
USED_G = [] # Boolean array: USED_G[num] is True if num is used
def solve_recursive(current_c_idx):
# Access global variables
global C_STR_G, N_G, MAX_BITS_N_G, RESULT_PERMUTATION_G, USED_G
count_placed_numbers = len(RESULT_PERMUTATION_G)
# Base case: N_G numbers have been placed in the permutation
if count_placed_numbers == N_G:
# If all of C_STR_G has been consumed, a solution is found
return current_c_idx == len(C_STR_G)
# If end of C_STR_G is reached but not all numbers are placed
if current_c_idx == len(C_STR_G):
return False
# --- Pruning based on remaining string length and numbers ---
remaining_numbers_to_place = N_G - count_placed_numbers
remaining_c_len = len(C_STR_G) - current_c_idx
# Not enough characters for remaining numbers (each needs at least 1 bit)
if remaining_c_len < remaining_numbers_to_place:
return False
# Too many characters (each takes at most MAX_BITS_N_G bits)
if remaining_c_len > remaining_numbers_to_place * MAX_BITS_N_G:
return False
# --- Pruning specific to current number S_i ---
# Current number S_i must start with '1' (since P_i >= 1 and no leading zeros)
if C_STR_G[current_c_idx] == '0':
return False
# Determine the maximum possible length for the binary string of the current number.
# It cannot be longer than MAX_BITS_N_G.
# It also cannot be so long that too few characters are left for subsequent numbers.
# Each of the (remaining_numbers_to_place - 1) numbers needs at least 1 bit.
if remaining_numbers_to_place == 1:
# If this is the last number to place, it must consume all remaining_c_len.
# (This is already a length constraint, not a loop range constraint for 'length' yet)
max_len_for_current_s_structurally = remaining_c_len
else:
# Max length current S_i can take, ensuring other (rem_nums - 1) numbers get at least 1 bit each.
max_len_for_current_s_structurally = remaining_c_len - (remaining_numbers_to_place - 1)
# The actual limit for the loop variable 'length' is min of MAX_BITS_N_G and this structural max.
limit_len_for_loop = min(MAX_BITS_N_G, max_len_for_current_s_structurally)
for length in range(1, limit_len_for_loop + 1):
substring = C_STR_G[current_c_idx : current_c_idx + length]
# Note: substring[0] is C_STR_G[current_c_idx]. We've already established it's '1'.
num = int(substring, 2)
# Pruning: If num is larger than N_G.
# Since lengths are tried in increasing order, and S_i starts with '1',
# if this num > N_G, any num formed by a longer substring will also be > N_G.
if num > N_G:
break
# num == 0 is impossible because substring[0] must be '1'.
# Check if number is not already used
if not USED_G[num]:
RESULT_PERMUTATION_G.append(num)
USED_G[num] = True
if solve_recursive(current_c_idx + length):
return True # Solution found, propagate True
# Backtrack: if solve_recursive returned False
USED_G[num] = False
RESULT_PERMUTATION_G.pop()
return False # No solution found from this state
def main():
global C_STR_G, N_G, MAX_BITS_N_G, RESULT_PERMUTATION_G, USED_G
C_STR_G = sys.stdin.readline().strip()
len_c = len(C_STR_G)
# --- Step 1: Determine N_G ---
# Max N can be 2^16 - 1 = 65535. Max |C| (983041) implies this.
# Precompute sum of lengths of binary representations up to this N.
max_n_for_sum_len_calc = 66000 # Sufficiently large to cover 65535
sum_of_lengths = [0] * (max_n_for_sum_len_calc + 1)
current_s = 0
for i in range(1, max_n_for_sum_len_calc + 1):
current_s += len(bin(i)[2:]) # bin(i)[2:] gives binary string without "0b"
sum_of_lengths[i] = current_s
# Find N_G such that sum_of_lengths[N_G] == len_c.
# Problem guarantees such N exists. We can use binary search.
found_N = -1
idx_low, idx_high = 1, max_n_for_sum_len_calc
while idx_low <= idx_high:
mid = idx_low + (idx_high - idx_low) // 2
if mid >= len(sum_of_lengths): # Boundary check for mid
idx_high = mid - 1
continue
if sum_of_lengths[mid] == len_c:
found_N = mid
break
elif sum_of_lengths[mid] < len_c:
idx_low = mid + 1
else: # sum_of_lengths[mid] > len_c
idx_high = mid - 1
N_G = found_N
if N_G == -1: # Should not happen given problem constraints
# Fallback linear scan if binary search fails (e.g. if array not perfectly searchable or max_N too small)
for i in range(1, max_n_for_sum_len_calc + 1):
if i < len(sum_of_lengths) and sum_of_lengths[i] == len_c:
N_G = i
break
if N_G == -1:
# This case indicates an issue or that N is larger than max_n_for_sum_len_calc.
# Given problem limits, max_n_for_sum_len_calc=66000 is fine.
return # Error
MAX_BITS_N_G = len(bin(N_G)[2:])
# Python's recursion limit might be an issue for large N_G.
# Max N_G is ~65535. Set limit higher.
sys.setrecursionlimit(max(N_G + 500, 70000))
# Initialize structures for the recursive solver
RESULT_PERMUTATION_G = []
USED_G = [False] * (N_G + 1) # 1-indexed for numbers 1 to N_G
# --- Step 2: Find the Permutation P ---
if solve_recursive(0):
print(*(RESULT_PERMUTATION_G))
else:
# This part should ideally not be reached if a solution is guaranteed.
# print("Solution not found.") # Or handle as error state
pass
if __name__ == '__main__':
main()