#1084063 (C++17) No.1694 ZerOne

• 問題: No.1694 ZerOne
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:16:42
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,729 bytes
• コンパイル時間: 1,472 ms
• コンパイル使用メモリ: 103,596 KB
• 実行使用メモリ: 44,704 KB
• 最終ジャッジ日時: 2025-05-14 13:18:21
• 合計ジャッジ時間: 5,067 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	TLE * 1 -- * 30

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
#include <utility> // for std::pair
#include <vector>

using namespace std;

// Use unsigned long long for storing string representations.
// N <= 60 fits within 64 bits.
typedef unsigned long long ull;

// Convert string S = s_0 s_1 ... s_{N-1} (0-indexed) to ull representation.
// Bit i represents character s_i. '1' sets the bit, '0' leaves it unset (0).
ull string_to_ull(const string& s) {
    ull res = 0;
    int N = s.length();
    for (int i = 0; i < N; ++i) {
        if (s[i] == '1') {
            // Set the i-th bit using bitwise OR and left shift
            res |= (1ULL << i);
        }
    }
    return res;
}

// Convert ull back to string of length N.
string ull_to_string(ull val, int N) {
    string s(N, '0'); // Initialize string with '0's
    for (int i = 0; i < N; ++i) {
        // Check if the i-th bit is set using bitwise AND and right shift
        if ((val >> i) & 1ULL) {
            s[i] = '1';
        }
    }
    return s;
}

int main() {
    // Faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string S_input;
    cin >> S_input;
    int N = S_input.length();

    // Base for mapping pairs (P0, P1) to a single number. Using N+1 guarantees uniqueness
    // since P0[k] and P1[k] are at most N.
    long long base = N + 1; 
    
    // Calculate maximum possible sum val(k2)+val(k3) to size the sum_map vector appropriately.
    // Max P0[k] or P1[k] is N.
    long long max_val_coord = N; 
    // Max value of val[k] = P0[k]*base + P1[k] is approx N*base + N.
    // Max sum val[k2]+val[k3] is approx 2 * (N * base + N).
    long long max_sum = 2 * (max_val_coord * base + max_val_coord);

    // Keep track of visited states using a hash set for O(1) average time lookups.
    unordered_set<ull> visited;
    // Use a queue for Breadth-First Search (BFS) to explore states level by level.
    queue<ull> q;

    // Initialize BFS with the starting string configuration.
    ull initial_val = string_to_ull(S_input);
    visited.insert(initial_val);
    q.push(initial_val);

    // Reusable vector to store mapping from sum value T = val(k2)+val(k3) to list of pairs {k2, k3}.
    // This avoids reallocating the vector in each iteration of the BFS loop.
    vector<vector<pair<int, int>>> sum_map(max_sum + 1);

    while (!q.empty()) {
        ull current_val = q.front();
        q.pop();

        // Convert current state value (ull) back to string format.
        string current_S = ull_to_string(current_val, N);

        // Calculate prefix sums P0 (count of '0's) and P1 (count of '1's) for current_S.
        // P0[k] stores count of '0's in the prefix S[0..k-1]. Size N+1.
        vector<int> P0(N + 1, 0);
        vector<int> P1(N + 1, 0);
        for (int i = 0; i < N; ++i) {
            P0[i + 1] = P0[i] + (current_S[i] == '0');
            P1[i + 1] = P1[i] + (current_S[i] == '1');
        }

        // Convert prefix sum pairs (P0[k], P1[k]) into single integer values val[k] using the base.
        // This allows using sums of pairs as keys/indices.
        vector<long long> val(N + 1);
        for (int k = 0; k <= N; ++k) {
            val[k] = (long long)P0[k] * base + P1[k];
        }

        // Clear the sum_map entries that were used in the previous state.
        // This could be optimized by tracking used indices, but clearing all is simpler.
        // The range is up to max_sum.
        // This part can be slow if max_sum is very large and the map is sparse.
        // But given N<=60, max_sum is manageable (~7400).
        // It's important to clear it because the prefix sums change with the string state.
        for(long long i=0; i <= max_sum; ++i) { 
           if (!sum_map[i].empty()) sum_map[i].clear();
        }

        // Populate sum_map: map T = val[k2]+val[k3] to list of pairs {k2, k3}.
        // Indices k relate to prefix sums P[k] for prefix S[0..k-1].
        // k2 is the length of prefix ending with substring t.
        // k3 is the length of prefix ending with middle substring m.
        // Ensure k2 > 0 (t non-empty) and k3 < N (u non-empty possible).
        for (int k2 = 1; k2 <= N; ++k2) { // k2 must be at least 1.
            for (int k3 = k2; k3 < N; ++k3) { // k3 must be less than N.
                long long T = val[k2] + val[k3];
                // Check bounds before accessing sum_map index.
                if (T >= 0 && T <= max_sum) { 
                   sum_map[T].push_back({k2, k3});
                }
            }
        }

        // Find possible swaps by iterating through all pairs of indices k1 and k4.
        // k1 is the length of prefix before t.
        // k4 is the length of prefix ending with u.
        // Condition: 0 <= k1 < k2 <= k3 < k4 <= N.
        for (int k1 = 0; k1 < N; ++k1) { // Minimum k1 = 0. Maximum k1 to allow swap is N-2.
            for (int k4 = k1 + 2; k4 <= N; ++k4) { // Minimum k4 = k1+2 to satisfy k1 < k2 <= k3 < k4. Maximum k4 = N.             
                long long S_sum = val[k1] + val[k4];
                // Check if S_sum is within valid range and if any pairs (k2,k3) generated this sum.
                if (S_sum >= 0 && S_sum <= max_sum && !sum_map[S_sum].empty()) {
                    // Iterate through all pairs (k2, k3) found for this required sum S_sum.
                    for (const auto& p : sum_map[S_sum]) {
                        int k2 = p.first;
                        int k3 = p.second;

                        // Validate the full sequence of indices according to problem constraints.
                        // Check: 0 <= k1 < k2 <= k3 < k4 <= N.
                        if (k1 < k2 && k3 < k4) { // k2 <= k3 is guaranteed by inner loop construction. Need check relative to k1, k4.
                            // The balance condition P(k2)-P(k1) == P(k4)-P(k3) is implicitly satisfied
                            // because we found S_sum = val[k1]+val[k4] matches T = val[k2]+val[k3].
                            
                            // Construct the new string by performing the swap operation.
                            // Recall: String S = prefix + t + m + u + suffix
                            // New string S' = prefix + u + m + t + suffix
                            // C++ substr uses 0-based indexing: substr(position, length).
                            string prefix = current_S.substr(0, k1);        // S[0..k1-1]
                            string t = current_S.substr(k1, k2 - k1);     // S[k1..k2-1]
                            string m = current_S.substr(k2, k3 - k2);     // S[k2..k3-1]
                            string u = current_S.substr(k3, k4 - k3);     // S[k3..k4-1]
                            string suffix = current_S.substr(k4);           // S[k4..N-1]
                            
                            string next_S = prefix + u + m + t + suffix;

                            // Convert the resulting string to its ull representation.
                            ull next_val = string_to_ull(next_S);

                            // If this new state (string) has not been visited before,
                            // add it to the visited set and enqueue it for exploration.
                            if (visited.find(next_val) == visited.end()) {
                                visited.insert(next_val);
                                q.push(next_val);
                            }
                        }
                    }
                }
            }
        }
    }

    // The final answer is the total number of unique states reachable from the initial string.
    cout << visited.size() << endl;

    return 0;
}