結果

問題 No.1056 2D Lamps
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:20:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 245 ms / 3,000 ms
コード長 7,533 bytes
コンパイル時間 1,141 ms
コンパイル使用メモリ 89,420 KB
実行使用メモリ 17,024 KB
最終ジャッジ日時 2025-05-14 13:21:41
合計ジャッジ時間 5,874 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <numeric> 
#include <algorithm> 
#include <cstdio> // For printf, fread
#include <cstdlib> // For atoi

// For bit manipulation functions like __builtin_ctzll or _BitScanForward64
#if defined(_MSC_VER)
#include <intrin.h>
#endif

const int ULL_BITS = 64;

struct MyBitset {
    std::vector<unsigned long long> bits;
    int n_squared; // Total number of bits conceptually
    int vec_size;  // Size of `bits` vector (number of unsigned long longs)

    MyBitset(int n_sq = 0) : n_squared(n_sq) {
        vec_size = (n_sq + ULL_BITS - 1) / ULL_BITS;
        bits.assign(vec_size, 0ULL);
    }

    void set(int k) {
        // Assumes 0 <= k < n_squared
        bits[k / ULL_BITS] |= (1ULL << (k % ULL_BITS));
    }

    bool get(int k) const {
        // Assumes 0 <= k < n_squared
        return (bits[k / ULL_BITS] >> (k % ULL_BITS)) & 1ULL;
    }

    MyBitset& operator^=(const MyBitset& other) {
        for (int i = 0; i < vec_size; ++i) {
            bits[i] ^= other.bits[i];
        }
        return *this;
    }

    bool operator==(const MyBitset& other) const {
        if (n_squared != other.n_squared) return false; // Should not happen if logic is correct
        for (int i = 0; i < vec_size; ++i) {
            if (bits[i] != other.bits[i]) {
                return false;
            }
        }
        return true;
    }

    int find_first_set_bit() const {
        for (int i = 0; i < vec_size; ++i) {
            if (bits[i] != 0ULL) {
                unsigned long long val = bits[i];
#if defined(__GNUC__) || defined(__clang__)
                return i * ULL_BITS + __builtin_ctzll(val);
#elif defined(_MSC_VER)
                unsigned long index;
                _BitScanForward64(&index, val);
                return i * ULL_BITS + index;
#else
                for (int j = 0; j < ULL_BITS; ++j) {
                    if ((val >> j) & 1ULL) {
                        return i * ULL_BITS + j;
                    }
                }
#endif
            }
        }
        return -1; 
    }
};

std::vector<MyBitset> basis_vectors_global; 
std::vector<int> pivot_cols_global;       

void build_basis(std::vector<MyBitset>& operation_vectors_mat, int n_squared) {
    // operation_vectors_mat is K x n_squared, will be modified into RRE form
    int K = operation_vectors_mat.size();
    
    int rank = 0;
    int current_col = 0; 
    // Transform matrix to RRE form
    // The first `rank` rows of operation_vectors_mat will be the basis
    for (current_col = 0; current_col < n_squared && rank < K; ++current_col) {
        int pivot_row_idx = rank;
        while(pivot_row_idx < K && !operation_vectors_mat[pivot_row_idx].get(current_col)){
            pivot_row_idx++;
        }

        if(pivot_row_idx < K){ 
            std::swap(operation_vectors_mat[rank], operation_vectors_mat[pivot_row_idx]); 
            
            for(int i=0; i < K; ++i){
                if(i != rank && operation_vectors_mat[i].get(current_col)){
                    operation_vectors_mat[i] ^= operation_vectors_mat[rank];
                }
            }
            rank++;
        }
    }
    
    // Store the computed basis (non-zero rows from RRE matrix)
    basis_vectors_global.clear();
    pivot_cols_global.clear();
    for (int i = 0; i < rank; ++i) {
        int p = operation_vectors_mat[i].find_first_set_bit();
        // For a matrix in RRE from this process, p should be the column where pivot was found.
        // If a row is all zeros, find_first_set_bit returns -1. We only add non-zero rows.
        if (p != -1) { 
            basis_vectors_global.push_back(operation_vectors_mat[i]);
            pivot_cols_global.push_back(p);
        }
    }
}

MyBitset reduce_board(const MyBitset& board_vec) {
    MyBitset temp_vec = board_vec;
    // Assumes basis_vectors_global are sorted by pivot_cols_global, 
    // or simply iterates through them. The Gaussian elimination produces pivots
    // in increasing column order, so pivot_cols_global will be sorted.
    for (size_t i = 0; i < basis_vectors_global.size(); ++i) {
        if (temp_vec.get(pivot_cols_global[i])) { // If bit at pivot position is 1
            temp_vec ^= basis_vectors_global[i];   // XOR with basis vector
        }
    }
    return temp_vec;
}

// Fast I/O
char io_buf[1 << 20]; // 1MB buffer
int io_buf_ptr = 0;
int io_buf_len = 0;

char get_char_fast() {
    if (io_buf_ptr >= io_buf_len) {
        io_buf_ptr = 0;
        io_buf_len = fread(io_buf, 1, sizeof(io_buf), stdin);
        if (io_buf_len == 0) return EOF;
    }
    return io_buf[io_buf_ptr++];
}

void read_string_fast(char* s) {
    char c = get_char_fast();
    while (c == ' ' || c == '\n' || c == '\r') c = get_char_fast();
    int i = 0;
    while (c != ' ' && c != '\n' && c != '\r' && c != EOF) {
        s[i++] = c;
        c = get_char_fast();
    }
    s[i] = '\0';
}

int read_int_fast() {
    char s[15]; // Max int string length
    read_string_fast(s);
    return atoi(s);
}


int main() {
    int N = read_int_fast();
    int M = read_int_fast();

    int n_squared = N * N;

    std::vector<MyBitset> operation_effect_vectors;
    // Rows (0 to N-1)
    for (int r_idx = 0; r_idx < N; ++r_idx) {
        MyBitset op(n_squared);
        for (int c_idx = 0; c_idx < N; ++c_idx) {
            op.set(r_idx * N + c_idx);
        }
        operation_effect_vectors.push_back(op);
    }
    // Cols (0 to N-1)
    for (int c_idx = 0; c_idx < N; ++c_idx) {
        MyBitset op(n_squared);
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            op.set(r_idx * N + c_idx);
        }
        operation_effect_vectors.push_back(op);
    }
    // Sum-diagonals: r+c = k_sum. k_sum from 0 to 2*(N-1)
    for (int k_sum = 0; k_sum <= 2 * (N - 1); ++k_sum) {
        MyBitset op(n_squared);
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            for (int c_idx = 0; c_idx < N; ++c_idx) {
                if (r_idx + c_idx == k_sum) {
                    op.set(r_idx * N + c_idx);
                }
            }
        }
        operation_effect_vectors.push_back(op);
    }
    // Diff-diagonals: r-c = k_diff. k_diff from -(N-1) to N-1
    for (int k_diff = -(N - 1); k_diff <= N - 1; ++k_diff) {
        MyBitset op(n_squared);
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            for (int c_idx = 0; c_idx < N; ++c_idx) {
                if (r_idx - c_idx == k_diff) {
                    op.set(r_idx * N + c_idx);
                }
            }
        }
        operation_effect_vectors.push_back(op);
    }
    
    build_basis(operation_effect_vectors, n_squared); // operation_effect_vectors is modified in place

    std::vector<MyBitset> canonical_boards(M, MyBitset(n_squared));
    char row_str[N + 5]; // Buffer for one row string, +5 for safety

    for (int m_idx = 0; m_idx < M; ++m_idx) {
        MyBitset current_board(n_squared);
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            read_string_fast(row_str);
            for (int c_idx = 0; c_idx < N; ++c_idx) {
                if (row_str[c_idx] == '#') {
                    current_board.set(r_idx * N + c_idx);
                }
            }
        }
        canonical_boards[m_idx] = reduce_board(current_board);
    }

    for (int i = 0; i < M; ++i) {
        for (int j = i + 1; j < M; ++j) {
            printf("%c", (canonical_boards[i] == canonical_boards[j] ? '1' : '0'));
        }
        if (i < M - 1) { 
            printf("\n");
        }
    }

    return 0;
}
0