結果

問題 No.1443 Andd
ユーザー qwewe
提出日時 2025-05-14 13:06:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,960 bytes
コンパイル時間 740 ms
コンパイル使用メモリ 90,244 KB
実行使用メモリ 16,728 KB
最終ジャッジ日時 2025-05-14 13:08:30
合計ジャッジ時間 13,929 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 3 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // Provides standard input/output stream objects (cin, cout)
#include <vector>   // Provides the vector container
#include <numeric>  // Provides numeric algorithms (not strictly needed here but generally useful)
#include <unordered_set> // Provides the unordered_set container (hash set)
#include <bitset>   // Provides the bitset container
#include <utility>  // Provides std::move

// Define the constant M = 2^10 = 1024 based on the problem constraint A_i < 2^10.
// Values less than M will be handled differently from values >= M.
const int M = 1024; 

int main() {
    // Optimize standard I/O operations by decoupling C++ streams from C stdio
    // and disabling synchronization. This typically speeds up input/output.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of elements in the sequence A
    std::cin >> N;

    // Declare a vector to store the sequence A. Use unsigned int because A_i are non-negative.
    std::vector<unsigned int> A(N); 
    // Read N integers into the vector A
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    // The state (set of possible values for X) is partitioned into two parts:
    // 1. Small values: Values strictly less than M. Stored efficiently in a std::bitset.
    // 2. Large values: Values greater than or equal to M. Stored in a std::unordered_set.
    
    // Bitset to track reachable values less than M. Size M represents indices 0 to M-1.
    std::bitset<M> current_bs_small;
    // Unordered_set (hash set) to track reachable values >= M. Using unsigned int for values.
    // The maximum possible value can reach N * max(A_i) ~ 2e4 * 1023 ~ 2e7, which fits in unsigned int.
    std::unordered_set<unsigned int> current_set_large; 

    // Initialize the state. Initially, X=0. Since 0 < M, it belongs to the small set.
    current_bs_small[0] = 1; // Mark 0 as reachable

    // Iterate through each element A[i] of the sequence, performing the operations.
    for (int i = 0; i < N; ++i) {
        // Prepare containers for the next state (after the i-th operation).
        // These will store the results of applying + A[i] and AND A[i] to the current reachable values.
        std::bitset<M> next_bs_small; // Next state's small values
        std::unordered_set<unsigned int> next_set_large; // Next state's large values
        // Optionally, we could reserve space in next_set_large for potential performance gains,
        // e.g., next_set_large.reserve(current_set_large.size() + M); but it's often fine without it.

        unsigned int current_A = A[i]; // The current element from sequence A

        // --- Process elements from the previous small set (values k_small < M) ---
        // Iterate through all possible small values from 0 to M-1.
        // A potential optimization for sparse bitsets is to use find_first/find_next,
        // but for M=1024, a simple loop is likely sufficient.
        for (int k_small = 0; k_small < M; ++k_small) {
            if (current_bs_small[k_small]) { // Check if k_small was a reachable value in the previous step
                
                // Option 1: Apply AND operation (k_small & current_A)
                unsigned int val_and = k_small & current_A;
                // Since k_small < M and current_A < M, the result val_and is guaranteed to be < M.
                next_bs_small[val_and] = 1; // Mark this result as reachable in the next small set
                
                // Option 2: Apply ADD operation (k_small + current_A)
                unsigned int val_add = k_small + current_A;
                if (val_add < M) {
                    // If the sum is still small, mark it as reachable in the next small set
                    next_bs_small[val_add] = 1;
                } else {
                    // If the sum becomes large (>= M), insert it into the next large set
                    next_set_large.insert(val_add);
                }
            }
        }
        
        // --- Process elements from the previous large set (values k_large >= M) ---
        // Iterate through each value k_large that was reachable and >= M in the previous step.
        for (unsigned int k_large : current_set_large) {
            
            // Option 1: Apply AND operation (k_large & current_A)
            unsigned int val_and = k_large & current_A;
            // Although k_large might be large, current_A < M = 2^10 has only bits up to index 9 set.
            // The AND operation `k_large & current_A` effectively zeros out bits at index 10 and higher.
            // Therefore, the result val_and is guaranteed to be <= current_A < M.
            next_bs_small[val_and] = 1; // Mark this result as reachable in the next small set
            
            // Option 2: Apply ADD operation (k_large + current_A)
            unsigned int val_add = k_large + current_A;
            // Since k_large >= M and current_A >= 0, the sum val_add is guaranteed to be >= M.
            next_set_large.insert(val_add); // Insert the result into the next large set
        }

        // Update the current state to the computed next state.
        // Using std::move can be more efficient as it avoids copying data if possible.
        current_bs_small = std::move(next_bs_small); 
        current_set_large = std::move(next_set_large);

        // Calculate the total number of distinct reachable values after this step.
        // It's the sum of the count of set bits in the small set bitset and the size of the large set.
        // The problem guarantees this count fits within a 31-bit integer. `size_t` is typically 64-bit, so it's safe.
        size_t total_size = current_bs_small.count() + current_set_large.size();
        
        // Output the total size for the current step i (after the i-th operation) followed by a newline.
        std::cout << total_size << "\n";
    }

    return 0; // Indicate successful execution
}
0