#1084190 (C++17) No.1056 2D Lamps

• 問題: No.1056 2D Lamps
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:24:06
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 191 ms / 3,000 ms
• コード長: 6,695 bytes
• コンパイル時間: 627 ms
• コンパイル使用メモリ: 72,408 KB
• 実行使用メモリ: 15,216 KB
• 最終ジャッジ日時: 2025-05-14 13:25:31
• 合計ジャッジ時間: 4,281 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 14

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:138:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  138 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:145:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  145 |             scanf("%s", line_buffer);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

#include <vector>
#include <string>
#include <bitset>
#include <algorithm> // For std::swap
#include <cstdio>    // For scanf/printf

// Using defines for constants as template arguments must be compile-time constants.
#define MAX_N_VAL 200
#define MAX_M_VAL 200
#define MAX_CELLS_VAL (MAX_N_VAL * MAX_N_VAL) // Max N*N = 40000
#define MAX_OPS_VAL (6 * MAX_N_VAL - 2)       // Max 6N-2 = 1198 for N=200. For N=1, it's 4.

// Global arrays for basis, pivots, and canonical forms
std::bitset<MAX_CELLS_VAL> basis[MAX_OPS_VAL];
int pivots[MAX_OPS_VAL];
int actual_rank = 0; // Number of vectors in the computed basis

std::bitset<MAX_CELLS_VAL> board_canonical_forms[MAX_M_VAL];
char line_buffer[MAX_N_VAL + 5]; // Buffer for reading rows with scanf

// Computes the basis for the vector space spanned by allowed operations.
// The basis vectors are stored in `basis` array, their pivots in `pivots`.
// `actual_rank` will store the dimension of this space.
void compute_basis(int N) {
    if (N == 0) { // Problem constraint N >= 1, so this case won't be hit.
        actual_rank = 0;
        return;
    }

    // Store all fundamental operation vectors temporarily.
    // The number of fundamental ops is 6N-2 for N >= 1.
    std::vector<std::bitset<MAX_CELLS_VAL>> op_vecs_list;
    op_vecs_list.reserve( (N == 0) ? 0 : (6 * N -2) ); // Reserve space

    // Row operations (N of them)
    // For 0-indexed row r_idx
    for (int r_idx = 0; r_idx < N; ++r_idx) {
        std::bitset<MAX_CELLS_VAL> op_v;
        for (int c_idx = 0; c_idx < N; ++c_idx) {
            op_v[r_idx * N + c_idx] = 1;
        }
        op_vecs_list.push_back(op_v);
    }

    // Column operations (N of them)
    // For 0-indexed column c_idx
    for (int c_idx = 0; c_idx < N; ++c_idx) {
        std::bitset<MAX_CELLS_VAL> op_v;
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            op_v[r_idx * N + c_idx] = 1;
        }
        op_vecs_list.push_back(op_v);
    }

    // Sum operations: r_idx + c_idx = k_sum (0-indexed sum)
    // k_sum from 0 to 2N-2. Total 2N-1 ops.
    for (int k_sum = 0; k_sum <= 2 * N - 2; ++k_sum) {
        std::bitset<MAX_CELLS_VAL> op_v;
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            int c_idx = k_sum - r_idx;
            if (c_idx >= 0 && c_idx < N) { // Check if (r_idx, c_idx) is within grid
                op_v[r_idx * N + c_idx] = 1;
            }
        }
        op_vecs_list.push_back(op_v);
    }
    
    // Difference operations: r_idx - c_idx + (N-1) = k_diff_shifted (0-indexed shifted diff)
    // k_diff_shifted from 0 to 2N-2. Total 2N-1 ops.
    for (int k_diff_shifted = 0; k_diff_shifted <= 2 * N - 2; ++k_diff_shifted) {
        std::bitset<MAX_CELLS_VAL> op_v;
        int target_diff = k_diff_shifted - (N - 1); // Original difference r_idx - c_idx
        for (int r_idx = 0; r_idx < N; ++r_idx) {
            int c_idx = r_idx - target_diff;
            if (c_idx >= 0 && c_idx < N) { // Check if (r_idx, c_idx) is within grid
                op_v[r_idx * N + c_idx] = 1;
            }
        }
        op_vecs_list.push_back(op_v);
    }
    
    actual_rank = 0;
    int num_total_ops = op_vecs_list.size(); // Should be 6N-2 for N >= 1

    // Gaussian elimination to find basis in Reduced Row Echelon Form (RREF)
    // Iterate through potential pivot columns (0 to N*N-1)
    // Iterate through rows of op_vecs_list to build basis up to 'actual_rank'
    for (int p_col = 0; p_col < N * N && actual_rank < num_total_ops; ++p_col) {
        int pivot_row_idx = actual_rank;
        // Find a row (from actual_rank onwards) that has a 1 in this p_col
        while (pivot_row_idx < num_total_ops && !op_vecs_list[pivot_row_idx][p_col]) {
            pivot_row_idx++;
        }

        if (pivot_row_idx < num_total_ops) { // Found a suitable row for pivot
            // Move this row to op_vecs_list[actual_rank] to be the next basis vector
            std::swap(op_vecs_list[actual_rank], op_vecs_list[pivot_row_idx]);
            
            // Record the pivot column for this new basis vector
            pivots[actual_rank] = p_col;

            // Eliminate the bit at p_col in all other rows in op_vecs_list
            // This step ensures the RRE form property (pivot column has 1 only at pivot row)
            for (int j = 0; j < num_total_ops; ++j) {
                if (j != actual_rank && op_vecs_list[j][p_col]) {
                    op_vecs_list[j] ^= op_vecs_list[actual_rank];
                }
            }
            actual_rank++; // Increment count of basis vectors found
        }
    }

    // Copy the computed basis vectors (which are now in op_vecs_list[0...actual_rank-1])
    // to the global 'basis' array for use in get_canonical_form.
    for(int i = 0; i < actual_rank; ++i) {
        basis[i] = op_vecs_list[i];
    }
}

// Computes canonical form of a given board state using the precomputed basis.
std::bitset<MAX_CELLS_VAL> get_canonical_form(const std::bitset<MAX_CELLS_VAL>& board_state) {
    std::bitset<MAX_CELLS_VAL> canonical_form = board_state;
    // For each basis vector (they are in RRE form, pivots are strictly increasing)
    for (int i = 0; i < actual_rank; ++i) {
        // If the bit at the pivot position of this basis vector is set in the current canonical_form,
        // XOR with this basis vector to clear that bit.
        if (canonical_form[pivots[i]]) {
            canonical_form ^= basis[i];
        }
    }
    return canonical_form;
}


int main() {
    // Using scanf/printf as suggested by the problem for performance.
    int N, M;
    scanf("%d %d", &N, &M);

    compute_basis(N); // Compute the basis once for the grid size N

    for (int m = 0; m < M; ++m) {
        std::bitset<MAX_CELLS_VAL> current_board; // Initialize to all zeros
        for (int r_idx = 0; r_idx < N; ++r_idx) { // Read N rows for the m-th board
            scanf("%s", line_buffer);
            for (int c_idx = 0; c_idx < N; ++c_idx) { // Read N characters for the r_idx-th row
                if (line_buffer[c_idx] == '#') {
                    // Map (r_idx, c_idx) to a single index for bitset
                    current_board[r_idx * N + c_idx] = 1;
                }
            }
        }
        board_canonical_forms[m] = get_canonical_form(current_board);
    }

    // Compare canonical forms and print results
    for (int i = 0; i < M - 1; ++i) {
        for (int j = i + 1; j < M; ++j) {
            if (board_canonical_forms[i] == board_canonical_forms[j]) {
                printf("1");
            } else {
                printf("0");
            }
        }
        printf("\n"); // Newline after each row of the output matrix
    }

    return 0;
}