結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,020 bytes |
| コンパイル時間 | 641 ms |
| コンパイル使用メモリ | 83,688 KB |
| 実行使用メモリ | 16,064 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:01 |
| 合計ジャッジ時間 | 10,983 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 TLE * 1 -- * 22 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <string_view> // Use string_view for efficiency to avoid copying substrings
// Global variables to store the state accessible by the recursive function
std::string C; // The concatenated binary string input
int N; // The size of the permutation (numbers 1 to N)
std::vector<bool> available; // Tracks which numbers from 1 to N are still available to be used
std::vector<int> result_permutation; // Stores the permutation being built / the final result
int max_len_N; // The maximum possible bit length for any number up to N
/**
* @brief Converts a binary string (represented by string_view) to its decimal integer value.
*
* @param bin_sv A string_view representing the binary string. Must contain only '0' and '1'.
* @return The decimal value of the binary string.
*/
long long binToDecView(std::string_view bin_sv) {
long long dec = 0;
// Efficient conversion using bit shifts.
// Assumes input contains only '0' and '1'.
// The maximum value N=65535 (16 bits) fits well within long long (64 bits).
for (char c : bin_sv) {
dec = (dec << 1) | (c - '0');
}
return dec;
}
/**
* @brief The recursive backtracking function to find a valid permutation.
*
* @param index The current starting index in the concatenated string C to parse from.
* @return True if a valid permutation is found from this state, False otherwise.
*/
bool solve(int index) {
// Base case: If we have successfully parsed the entire string C
if (index == C.length()) {
// A valid partition covers the entire string C.
// We also need to ensure exactly N numbers were used.
// This check confirms we formed a complete permutation of 1..N.
return result_permutation.size() == N;
}
// Determine the maximum length for the next binary string segment we can try.
// It cannot be longer than the remaining part of C, nor longer than the maximum
// bit length required for any number up to N.
int current_max_len = std::min(max_len_N, (int)C.length() - index);
// Iterate through all possible lengths `l` for the next number's binary representation.
for (int l = 1; l <= current_max_len; ++l) {
// Extract the substring of length `l` starting at `index`.
// Use string_view to avoid expensive string copying.
std::string_view sub = std::string_view(C).substr(index, l);
// The binary representation of any integer P_i >= 1 must start with '1'
// (no leading zeros allowed). Check this condition.
if (sub[0] == '0') continue; // Skip if it starts with '0'
// Convert the binary substring `sub` to its integer value `k`.
long long k_ll = binToDecView(sub);
// Check if the obtained integer `k` is valid for the permutation:
// 1. Must be positive (i.e., >= 1).
// 2. Must not exceed N (the upper bound of the permutation range).
if (k_ll <= 0 || k_ll > N) {
continue; // k is outside the valid range {1, ..., N}
}
int k = (int)k_ll; // Safe to cast to int because 1 <= k_ll <= N <= 65535 fits in standard int.
// Check if the number `k` is available (i.e., hasn't been used yet in the permutation)
if (available[k]) {
// Try including k in the permutation
available[k] = false; // Mark k as used
result_permutation.push_back(k); // Add k to the current sequence being built
// Recursively call solve for the remainder of the string C, starting after the current segment.
if (solve(index + l)) {
// If the recursive call finds a solution, it means we found a valid complete permutation.
// Propagate true up the call stack.
return true;
}
// Backtrack: If the choice of `k` did not lead to a solution, undo the choice.
result_permutation.pop_back(); // Remove k from the sequence
available[k] = true; // Mark k as available again, allowing other paths to use it.
}
}
// If we tried all possible lengths `l` from the current `index` and none led to a solution,
// then this path is invalid. Return false.
return false;
}
/**
* @brief Calculates the number of bits in the binary representation of integer k (without leading zeros).
* Equivalent to floor(log2(k)) + 1 for k > 0.
*
* @param k The positive integer.
* @return The number of bits required. Returns 0 for k <= 0.
*/
long long integer_bit_length(int k) {
if (k <= 0) return 0; // Bit length is defined for positive integers.
// Calculate bit length using integer operations (safer than float log2).
long long len = 0;
unsigned int tempK = k; // Use unsigned type for right bit shifts to avoid potential sign extension issues.
while (tempK > 0) {
tempK >>= 1; // Right shift by 1 is equivalent to dividing by 2.
len++;
}
// Example: k=1 (0b1) -> len=1. k=2 (0b10) -> len=2. k=3 (0b11) -> len=2. k=4 (0b100) -> len=3.
// This correctly computes the number of bits.
return len;
}
int main() {
// Use fast I/O operations for performance critical competitive programming tasks.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> C; // Read the concatenated binary string input C.
long long target_len = C.length(); // The required total length of concatenated binary strings.
// Problem constraints state |C| >= 1, so target_len will be at least 1.
// Determine the value of N by summing the bit lengths of integers 1, 2, ..., N
// until the total length matches target_len.
long long current_len = 0;
N = 0; // Start counting N from 1.
while(current_len < target_len) {
N++;
// Basic check to prevent infinite loop or overflow if N becomes unexpectedly large.
// Maximum N is 65535 based on max |C|, safely within int range.
if (N <= 0) return 1; // Error state check.
current_len += integer_bit_length(N); // Add the bit length of the current number N.
}
// Verify that the calculated total length matches the input string length.
// The problem guarantees that such an N exists and a permutation can be formed.
if (current_len != target_len) {
// This case indicates an inconsistency, potentially a bug or misinterpretation.
// According to the problem, this should not happen.
return 1; // Exit with error code.
}
// Calculate the maximum bit length required for any number in the range 1..N.
// This is simply the bit length of N itself.
max_len_N = integer_bit_length(N);
// Initialize data structures needed for the backtracking search.
// `available` vector tracks usage of numbers 1 to N. Size N+1 for 1-based indexing.
available.resize(N + 1, true);
available[0] = false; // Index 0 is unused.
// `result_permutation` will store the found sequence. Reserve space for N elements
// to potentially improve performance by avoiding reallocations during push_back.
result_permutation.reserve(N);
// Start the backtracking search from the beginning of the string C (index 0).
if (!solve(0)) {
// If solve(0) returns false, it means no solution was found.
// This contradicts the problem statement's guarantee that a solution exists.
// Indicates a potential issue with the logic or implementation.
return 1; // Exit with error code.
}
// Print the found permutation elements, separated by spaces.
for (int i = 0; i < result_permutation.size(); ++i) {
std::cout << result_permutation[i] << (i == result_permutation.size() - 1 ? "" : " ");
}
std::cout << std::endl; // Ensure the output ends with a newline character.
return 0; // Indicate successful execution.
}