#1083747 (C++17) No.2270 T0空間

• 問題: No.2270 T0空間
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:59:22
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 122 ms / 2,000 ms
• コード長: 7,098 bytes
• コンパイル時間: 1,044 ms
• コンパイル使用メモリ: 91,280 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:00:34
• 合計ジャッジ時間: 4,771 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
other	AC * 22

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // for std::sort
#include <utility> // for std::pair and std::move

// Use unsigned long long for 64-bit integers to store segments of column data.
// This allows packing 64 bits of column data into a single integer.
using ull = unsigned long long;

// Fast I/O setup function to potentially speed up input/output operations.
void fast_io() {
    // Disable synchronization between C++ standard streams and C stdio library.
    // This can significantly speed up cin/cout operations.
    std::ios_base::sync_with_stdio(false);
    // Untie cin from cout. By default, cin flushes cout before reading.
    // Untying them removes this overhead.
    std::cin.tie(NULL);
}

int main() {
    // Apply fast I/O settings.
    fast_io();

    int N; // Length of the binary strings. Also the number of columns to consider.
    std::cin >> N;

    int M; // Number of binary strings in the set S. Also the length of each column.
    std::cin >> M;

    // Handle the edge case where N=1.
    // The condition involves pairs of distinct indices n0, n1 <= N.
    // If N=1, the only index is 1. There are no pairs of distinct indices.
    // Therefore, the condition is vacuously true.
    if (N <= 1) { 
        std::cout << "Yes\n";
        return 0;
    }

    // Calculate the number of 64-bit unsigned long long integers required to store M bits.
    // Each column has M bits (one bit from each string). We represent each column's data
    // as a vector of ull integers. W is the size of this vector.
    // This is equivalent to ceil(M / 64.0). Using integer division: (M + 64 - 1) / 64
    int W = (M + 63) / 64; 
    
    // Declare a vector of vectors to store the column data.
    // `columns[j]` will store the data for the column corresponding to the (j+1)-th character from the right.
    // It's a vector of N elements, where each element is a vector of W unsigned long longs, initialized to 0.
    std::vector<std::vector<ull>> columns(N, std::vector<ull>(W, 0ULL));

    // Create a string buffer `s_m` to read input strings.
    std::string s_m;
    // Reserve capacity for the string based on N. This is an optimization to potentially
    // avoid memory reallocations if N is large, as each string will have length N.
    // We check N > 0, which is true since we handled N <= 1 already.
    s_m.reserve(N);

    // Read M strings one by one.
    for (int m = 0; m < M; ++m) {
        std::cin >> s_m;
        // The problem constraints guarantee that the input string `s_m` has length N.

        // Iterate through each character of the string `s_m`.
        for (int k = 0; k < N; ++k) {
            // `k` is the 0-based index from the left of the string `s_m`.
            // The character `s_m[k]` corresponds to the (N-k)-th character counting from the right (1-based).
            
            // We need to map this character to its corresponding column index `j`.
            // We use 0-based column indices: `j` ranges from 0 to N-1.
            // Column `j` represents the data for the (j+1)-th character from the right.
            // The relationship is: (j+1) = N-k  =>  j = N-k-1.
            int j = N - 1 - k; 
            
            // If the character is '1', we need to set the corresponding bit in the column vector `columns[j]`.
            if (s_m[k] == '1') {
                // The m-th string (0-indexed) contributes the m-th bit to this column.
                // We need to determine which 64-bit integer block `p` within `columns[j]` this bit belongs to.
                int p = m / 64; // Integer division gives the block index.
                // We also need the specific bit position `bit_idx` (0-63) within that block `columns[j][p]`.
                int bit_idx = m % 64; // Modulo operation gives the bit index within the block.
                
                // Set the bit using bitwise OR operation.
                // `1ULL` ensures the literal 1 is treated as an unsigned long long type. This is crucial
                // especially for shifts >= 32 bits on systems where long might be 32 bits.
                columns[j][p] |= (1ULL << bit_idx);
            }
            // If `s_m[k]` is '0', the corresponding bit should remain 0. Since we initialized `columns` with 0s,
            // no action is required for '0' characters.
        }
    }

    // To check for identical columns efficiently, we sort the columns.
    // We create pairs of (column_vector, original_column_index) to keep track of the original position if needed,
    // but primarily to facilitate sorting based on the vector data.
    std::vector<std::pair<std::vector<ull>, int>> indexed_columns(N);
    for (int j = 0; j < N; ++j) {
        // Use `std::move` to transfer ownership of the `columns[j]` vector data to the pair.
        // This is more efficient than copying, especially for large vectors (large W).
        // After the move, `columns[j]` is left in a valid but unspecified state.
        indexed_columns[j] = {std::move(columns[j]), j}; 
    }
    
    // The original `columns` vector now contains moved-from vectors. It's no longer needed.
    // Clearing it can potentially release memory earlier. `shrink_to_fit` requests deallocation.
    columns.clear();
    columns.shrink_to_fit(); 

    // Sort the `indexed_columns` vector. The `std::sort` algorithm uses `operator<` for pairs by default.
    // Pair comparison first compares the `first` elements. For `std::vector`, `operator<` performs
    // lexicographical comparison, which compares the column data bit patterns correctly.
    std::sort(indexed_columns.begin(), indexed_columns.end());

    // After sorting, identical columns will be adjacent in the `indexed_columns` vector.
    // We iterate through the sorted list and check adjacent pairs.
    bool found_duplicate = false;
    for (int i = 0; i < N - 1; ++i) {
        // Compare the `first` element (the column vector) of adjacent pairs.
        // `std::vector::operator==` compares vectors element by element.
        if (indexed_columns[i].first == indexed_columns[i+1].first) {
           // If two adjacent vectors are identical, it means we found two columns with the same bit pattern.
           // Since N > 1 and we included all N columns, these identical vectors must correspond to
           // distinct original column positions (indices j). This violates the problem's condition.
           found_duplicate = true;
           // Once a duplicate pair is found, we know the answer is "No", so we can stop checking.
           break; 
        }
    }

    // Output the final result based on whether any duplicate columns were found.
    if (found_duplicate) {
        // If duplicates were found, the set S is not a "good bit string set".
        std::cout << "No\n";
    } else {
        // If the loop finished without finding any duplicates, all columns are distinct.
        // The set S satisfies the condition and is a "good bit string set".
        std::cout << "Yes\n";
    }

    return 0; // Indicate successful execution.
}