結果
| 問題 |
No.1694 ZerOne
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,059 bytes |
| コンパイル時間 | 1,401 ms |
| コンパイル使用メモリ | 101,256 KB |
| 実行使用メモリ | 121,420 KB |
| 最終ジャッジ日時 | 2025-05-14 13:11:00 |
| 合計ジャッジ時間 | 4,660 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 30 |
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <set> // To store unique reachable strings
#include <queue> // For BFS queue
#include <map> // To map counts to substring locations
#include <vector> // To store list of locations
#include <utility> // For std::pair
int main() {
// Use faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::string S; // Input string
std::cin >> S;
std::set<std::string> reachable; // Set to store all unique strings reachable from S
std::queue<std::string> q; // Queue for BFS traversal
// Initialize BFS
reachable.insert(S);
q.push(S);
int N = S.length(); // Length of the string
// Start BFS
while (!q.empty()) {
std::string current_S = q.front(); // Get the current string to process
q.pop(); // Remove it from the queue
// Precompute prefix sums for the current string `current_S`
// prefix_sums[i] stores the count of 0s (first) and 1s (second) in the prefix current_S[0...i-1]
std::vector<std::pair<int, int>> prefix_sums(N + 1);
prefix_sums[0] = {0, 0}; // Base case: empty prefix has zero 0s and 1s
for (int i = 0; i < N; ++i) {
prefix_sums[i+1] = prefix_sums[i]; // Copy counts from previous prefix
if (current_S[i] == '0') {
prefix_sums[i+1].first++; // Increment count of 0s
} else {
prefix_sums[i+1].second++; // Increment count of 1s
}
}
// Create a map to store locations of all substrings, grouped by their (count0, count1)
// Key: std::pair<int, int> representing the counts (number of 0s, number of 1s)
// Value: std::vector<std::pair<int, int>> storing pairs of [L, R] indices (1-based) for substrings with these counts
std::map<std::pair<int, int>, std::vector<std::pair<int, int>>> count_to_indices;
// Iterate through all possible start and end indices to find all substrings
for (int i = 0; i < N; ++i) { // Start index (0-based)
for (int j = i; j < N; ++j) { // End index (0-based)
int L = i + 1; // Convert to 1-based start index L
int R = j + 1; // Convert to 1-based end index R
// Calculate the counts of 0s and 1s for the substring S[L..R] using prefix sums
// The counts for S[L..R] (which is S[L-1..R-1] in 0-based indexing) is P[R] - P[L-1]
std::pair<int, int> counts = {prefix_sums[R].first - prefix_sums[L-1].first, prefix_sums[R].second - prefix_sums[L-1].second};
// Store the location [L, R] associated with its counts
// We only care about non-empty substrings. The loop condition i<=j ensures R>=L.
count_to_indices[counts].push_back({L, R});
}
}
// Iterate through the map. For each distinct count vector, check pairs of substrings.
for (auto const& [counts, locations] : count_to_indices) {
// Skip counts (0,0) which correspond to empty substrings. This check is mostly for safety.
if (counts.first == 0 && counts.second == 0) continue;
int k = locations.size(); // Number of substrings found with this count vector
// If there are fewer than 2 substrings with these counts, we cannot perform a swap.
if (k < 2) continue;
// Iterate through all distinct pairs of locations (i, j) for the current count vector
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
// Consider the pair of substrings defined by locations[i] and locations[j]
// Let's test if locations[i] can be substring t and locations[j] can be substring u
int Lt1 = locations[i].first;
int Rt1 = locations[i].second;
int Lu1 = locations[j].first;
int Ru1 = locations[j].second;
// Check the non-overlapping condition: t must end before u begins (Rt < Lu)
if (Rt1 < Lu1) {
// Extract the actual substrings t and u from current_S
// std::string::substr uses 0-based index and length
// Substring S[L..R] corresponds to indices L-1 to R-1
// Length is R - L + 1
std::string t = current_S.substr(Lt1 - 1, Rt1 - Lt1 + 1);
std::string u = current_S.substr(Lu1 - 1, Ru1 - Lu1 + 1);
// Construct the new string `next_S` by swapping t and u: S = A t B u C -> S' = A u B t C
std::string next_S = "";
// Part A: S[1..Lt1-1] => indices 0 to Lt1-2
if (Lt1 > 1) next_S += current_S.substr(0, Lt1 - 1);
// Part u
next_S += u;
// Part B: S[Rt1+1..Lu1-1] => indices Rt1 to Lu1-2. Exists if Lu1-1 >= Rt1+1 => Lu1 > Rt1+1
if (Lu1 > Rt1 + 1) next_S += current_S.substr(Rt1, Lu1 - 1 - Rt1);
// Part t
next_S += t;
// Part C: S[Ru1+1..N] => indices Ru1 to N-1. Exists if N > Ru1
if (N > Ru1) next_S += current_S.substr(Ru1);
// If the generated string `next_S` is new (not visited before)
if (reachable.find(next_S) == reachable.end()) {
reachable.insert(next_S); // Add it to the set of reachable strings
q.push(next_S); // Add it to the BFS queue to explore further
}
}
// Now test if locations[j] can be substring t and locations[i] can be substring u
// This is needed because the order in the `locations` vector might not correspond to string order
int Lt2 = locations[j].first;
int Rt2 = locations[j].second;
int Lu2 = locations[i].first;
int Ru2 = locations[i].second;
// Check the non-overlapping condition: t must end before u begins (Rt < Lu)
if (Rt2 < Lu2) {
// Extract substrings t and u
std::string t = current_S.substr(Lt2 - 1, Rt2 - Lt2 + 1);
std::string u = current_S.substr(Lu2 - 1, Ru2 - Lu2 + 1);
// Construct the new string S' = A u B t C
std::string next_S = "";
// Part A: S[1..Lt2-1]
if (Lt2 > 1) next_S += current_S.substr(0, Lt2 - 1);
// Part u
next_S += u;
// Part B: S[Rt2+1..Lu2-1]
if (Lu2 > Rt2 + 1) next_S += current_S.substr(Rt2, Lu2 - 1 - Rt2);
// Part t
next_S += t;
// Part C: S[Ru2+1..N]
if (N > Ru2) next_S += current_S.substr(Ru2);
// If the generated string `next_S` is new
if (reachable.find(next_S) == reachable.end()) {
reachable.insert(next_S); // Add to set
q.push(next_S); // Add to queue
}
}
}
}
}
}
// After BFS completes, the size of the `reachable` set is the answer
std::cout << reachable.size() << std::endl;
return 0;
}