結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,715 bytes |
| コンパイル時間 | 1,241 ms |
| コンパイル使用メモリ | 98,216 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:08 |
| 合計ジャッジ時間 | 11,331 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 TLE * 1 -- * 22 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>
#include <set>
#include <vector>
// For compiler intrinsics used in binLength:
#ifdef _MSC_VER // Check if compiling with MSVC
#include <intrin.h> // Include for _BitScanReverse64
#else
#include <climits> // Include for CHAR_BIT (used with __builtin_clzll)
#endif
using namespace std;
// Global variables
string C; // The concatenated binary string input
long long N; // The size of the permutation (1 to N), determined from L
long long L; // Length of the input string C
vector<long long> P; // Stores the current permutation path being explored during backtracking
set<long long> used_numbers; // Tracks numbers used in the current path using a set for quick lookups
bool solution_found = false;// Flag to stop the backtracking search once the first solution is found
/*
* Calculates the length of the standard binary representation of a positive integer k.
* Uses compiler intrinsics for efficiency. Assumes k > 0.
* For MSVC, uses _BitScanReverse64 to find the index of the most significant bit (MSB). Length = MSB index + 1.
* For GCC/Clang, uses __builtin_clzll to count leading zeros. Length = Total bits - leading zeros.
*/
int binLength(unsigned long long k) {
if (k == 0) return 0; // Base case or error, problem states P_i >= 1
#ifdef _MSC_VER
// MSVC specific intrinsic
if (k == 0) return 0; // _BitScanReverse64 requires non-zero input
unsigned long index;
_BitScanReverse64(&index, k); // Find the 0-based index of the MSB
return (int)index + 1; // Length is index + 1
#else
// GCC/Clang specific intrinsic
if (k == 0) return 0; // __builtin_clzll requires non-zero input
// Calculate length based on number of leading zeros
// sizeof(unsigned long long) * CHAR_BIT gives total bits (usually 64)
return (sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(k);
#endif
}
/*
* Recursive backtracking function to find a valid permutation P.
* It explores partitions of the string C starting from `index`.
*/
void solve(int index) {
// If a solution has already been found in another recursive branch, prune this one
if (solution_found) {
return;
}
// Base Case: Successfully parsed the entire string C
if (index == L) {
// Check if exactly N numbers were used (meaning we formed a complete permutation of 1..N)
if (used_numbers.size() == N) {
solution_found = true; // Set flag indicating a solution is found
}
return; // Return from this path
}
// Pruning checks:
// If current index is beyond string length, or already used N items before reaching end
if (index > L || used_numbers.size() >= N) {
return; // Invalid path, backtrack
}
// Pruning: Standard binary representations must start with '1'
if (C[index] == '0') {
return; // Invalid path, cannot start a number with '0', backtrack
}
// Determine the maximum possible length of a binary string for numbers up to N
// This helps prune branches where the length 'l' becomes too large.
int max_len = 0;
if (N > 0) max_len = binLength(N);
unsigned long long current_val_calc = 0; // Variable to store the decimal value of the current substring being considered
// Iterate through possible lengths 'l' for the next number in the permutation
for (int l = 1; index + l <= L; ++l) {
// Pruning: If length 'l' exceeds the max possible length for numbers up to N, stop trying longer lengths
if (l > max_len) {
break;
}
// Calculate the decimal value represented by C[index .. index+l-1] efficiently
// Use bit shift left (multiply by 2) and add the new bit (C[index + l - 1] - '0')
current_val_calc = (current_val_calc << 1) | (C[index + l - 1] - '0');
// Pruning: If the current calculated value already exceeds N, any longer string starting at this index will also represent a value > N.
if (current_val_calc > N) {
break;
}
// Ensure value is positive (problem states P_i >= 1)
if (current_val_calc == 0) continue;
// Critical Check: Verify if the current length 'l' matches the standard binary representation length for 'current_val_calc'
// This ensures we use standard representations (e.g., "1" for 1, not "01") and correct number interpretation.
if (binLength(current_val_calc) == l) {
// Check if the current number 'current_val_calc' has NOT been used yet in this path
// uses set::find for O(log N) lookup on average.
if (used_numbers.find(current_val_calc) == used_numbers.end()) {
// Choose: Add the number to the used set and the permutation path vector
used_numbers.insert(current_val_calc);
P.push_back(current_val_calc);
// Explore: Recursively call 'solve' for the next index position (index + l)
solve(index + l);
// If the recursive call found a solution, stop searching in this branch and return
if (solution_found) {
return;
}
// Backtrack: Remove the number from the used set and path vector (undo the choice)
P.pop_back();
used_numbers.erase(current_val_calc);
}
}
}
}
/*
* Function to calculate f(N) = sum of lengths of binary representations for k=1..N
* Uses the derived formula: MN + M + 1 - 2^M, where M = binLength(N) = floor(log2 N) + 1
* This formula computes the total length of the concatenated string C for a permutation of 1..N.
*/
unsigned long long calculate_f_final_formula(long long k) {
// Base case: f(0) = 0
if (k <= 0) return 0;
unsigned long long uk = k; // Use unsigned long long for calculations
int M = binLength(uk); // M is the number of bits in binary representation of k
unsigned long long K_ull = k; // N as unsigned long long
unsigned long long M_ull = M; // M as unsigned long long
if (M == 0) return 0; // Should not happen for k >= 1
// Calculate 2^M safely using bit shift. Check for M=64 edge case if N could be very large.
// For N <= 65535, M <= 16, so 1ULL << M_ull is safe.
unsigned long long pow2M = (M_ull < 64) ? (1ULL << M_ull) : 0; // Placeholder for M=64, not reachable here
// Apply the formula: MN + M + 1 - 2^M
// Max intermediate M*K approx 16 * 65535 ~ 1M, fits well within unsigned long long.
unsigned long long result = M_ull * K_ull + M_ull + 1 - pow2M;
return result;
}
int main() {
// Optimize C++ standard I/O streams for speed
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> C; // Read the input concatenated binary string C
L = C.length(); // Store its length
// Binary search to find the value N such that f(N) = L
// The search range is [1, 65535] based on problem constraints (max L corresponds to N=2^16-1)
long long low = 1, high = 65535;
long long found_N = -1; // Variable to store the found N
while(low <= high) {
long long mid = low + (high - low) / 2; // Calculate midpoint safely to avoid overflow
if (mid <= 0) { // Ensure mid is positive
low = 1; continue;
}
unsigned long long current_L = calculate_f_final_formula(mid); // Calculate f(mid)
if (current_L == L) { // Found the exact N
found_N = mid;
break; // Exit loop, N found
} else if (current_L < L) { // f(mid) is too small, need larger N -> search in upper half
low = mid + 1;
} else { // current_L > L -> f(mid) is too large, need smaller N -> search in lower half
high = mid - 1;
}
}
N = found_N; // Assign the found value of N
// Check if N was found. Problem guarantees it exists.
if (N == -1) {
// Error case: N not found. Should not happen based on problem guarantees.
return 1; // Indicate error
}
// Initiate the backtracking search starting from index 0 of string C
solve(0);
// Print the resulting permutation P found by the backtracking search
for (int i = 0; i < P.size(); ++i) {
cout << P[i] << (i == P.size() - 1 ? "" : " "); // Print space separated values
}
cout << endl; // Print final newline
return 0; // Indicate successful execution
}