結果

問題 No.1056 2D Lamps
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:56:09
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 3,479 bytes
記録
コンパイル時間 2,427 ms
コンパイル使用メモリ 213,852 KB
実行使用メモリ 28,556 KB
最終ジャッジ日時 2025-04-09 20:57:33
合計ジャッジ時間 8,292 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

const int MAX_VAR = 1200; // 6*200 - 2 = 1198 for N=200

struct Bitset {
    vector<uint64_t> bits;
    int n;
    Bitset(int size) : n(size) {
        bits.resize((size + 63) / 64, 0);
    }
    void set(int pos) {
        bits[pos / 64] |= 1ULL << (pos % 64);
    }
    bool get(int pos) const {
        return (bits[pos / 64] >> (pos % 64)) & 1;
    }
    void toggle(const Bitset& other) {
        for (int i = 0; i < bits.size(); ++i) {
            bits[i] ^= other.bits[i];
        }
    }
};

int gauss(vector<Bitset>& equations, vector<bool>& constants, int var_count) {
    int n = equations.size();
    int rank = 0;
    vector<int> pivot_row(var_count, -1);
    for (int col = 0; col < var_count; ++col) {
        int pivot = -1;
        for (int row = rank; row < n; ++row) {
            if (equations[row].get(col)) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(equations[rank], equations[pivot]);
        swap(constants[rank], constants[pivot]);
        for (int row = 0; row < n; ++row) {
            if (row != rank && equations[row].get(col)) {
                equations[row].toggle(equations[rank]);
                constants[row] = constants[row] ^ constants[rank];
            }
        }
        rank++;
    }
    for (int row = rank; row < n; ++row) {
        if (constants[row]) {
            return -1; // No solution
        }
    }
    return 0; // Solution exists
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<vector<string>> grids(M);
    for (int i = 0; i < M; ++i) {
        grids[i].resize(N);
        for (int j = 0; j < N; ++j) {
            cin >> grids[i][j];
        }
    }
    int var_count = 6 * N - 2;
    vector<string> ans;
    for (int i = 0; i < M; ++i) {
        for (int j = i + 1; j < M; ++j) {
            vector<Bitset> equations;
            vector<bool> constants;
            for (int x = 0; x < N; ++x) {
                for (int y = 0; y < N; ++y) {
                    bool diff = (grids[i][x][y] != grids[j][x][y]);
                    Bitset eq(var_count);
                    // row x (0..N-1)
                    eq.set(x);
                    // column y (N..2N-1)
                    eq.set(N + y);
                    // sum s (x+1) + (y+1) = k = x+y+2. So k ranges from 2 to 2N. indices 2N.. 2N + (2N-1) -1 = 4N-2 ?
                    int sum_k = (x + 1) + (y + 1);
                    int sum_idx = 2 * N + (sum_k - 2); // sum_k starts at 2, subtract 2 to start from 0
                    eq.set(2 * N + sum_k - 2);
                    // diff diag: (x+1) - (y+1) = l = x - y. ranges from -(N-1) to N-1. add (N-1) to make it 0..2N-2
                    int diff_l = (x + 1) - (y + 1);
                    int diff_idx = 2 * N + (2 * N - 1) + (diff_l + (N - 1));
                    eq.set(diff_idx);
                    equations.push_back(eq);
                    constants.push_back(diff);
                }
            }
            int res = gauss(equations, constants, var_count);
            ans.push_back(res == 0 ? "1" : "0");
        }
    }
    int idx = 0;
    for (int i = 0; i < M - 1; ++i) {
        for (int j = i + 1; j < M; ++j) {
            if (j > i + 1) cout << ans[idx++];
            else cout << ans[idx++];
        }
        if (i < M - 2) cout << '\n';
    }
    cout << endl;
    return 0;
}
0