結果
問題 |
No.1056 2D Lamps
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:01:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,542 bytes |
コンパイル時間 | 1,997 ms |
コンパイル使用メモリ | 200,920 KB |
実行使用メモリ | 25,188 KB |
最終ジャッジ日時 | 2025-04-09 21:02:48 |
合計ジャッジ時間 | 17,681 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 TLE * 1 -- * 9 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MAX_N = 200; const int MAX_SIZE = MAX_N * MAX_N; using BitSet = bitset<MAX_SIZE>; vector<BitSet> line_vectors; BitSet basis[MAX_SIZE]; // basis[i] is the vector with pivot at position i int pivot[MAX_SIZE]; // pivot[i] is the index of the basis vector with pivot i int basis_size; void add_vector(BitSet vec) { for (int i = MAX_SIZE - 1; i >= 0; --i) { if (vec[i]) { if (!basis[i].any()) { basis[i] = vec; pivot[i] = basis_size++; return; } else { vec ^= basis[i]; } } } } bool is_in_span(BitSet vec) { for (int i = MAX_SIZE - 1; i >= 0; --i) { if (vec[i]) { if (basis[i].any()) { vec ^= basis[i]; } else { return false; } } } return vec.none(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; int cell_count = N * N; // Generate all line vectors line_vectors.reserve(4*N); // Rows for (int i = 0; i < N; ++i) { BitSet vec; for (int j = 0; j < N; ++j) { int pos = i * N + j; vec.set(pos); } line_vectors.push_back(vec); } // Columns for (int j = 0; j < N; ++j) { BitSet vec; for (int i = 0; i < N; ++i) { int pos = i * N + j; vec.set(pos); } line_vectors.push_back(vec); } // Sum diagonals (i + j = k) // k ranges from 2 to 2N for (int k = 2; k <= 2*N; ++k) { BitSet vec; for (int i = 0; i < N; ++i) { int j = k - (i + 1) - 1; // convert to 1-based i,j if (j >= 0 && j < N) { int pos = i * N + j; vec.set(pos); } } line_vectors.push_back(vec); } // Anti-diagonals (i - j) + (N-1) = k, 0<=k<=2N-2 for (int k = 0; k <= 2*N-2; ++k) { BitSet vec; int d = k - (N-1); for (int i = 0; i < N; ++i) { int j = i - d; if (j >=0 && j < N) { int pos = i * N + j; vec.set(pos); } } line_vectors.push_back(vec); } // Perform Gaussian elimination to find the basis basis_size = 0; memset(pivot, -1, sizeof(pivot)); for (const auto& vec : line_vectors) { BitSet temp = vec; add_vector(temp); } // Read M configurations vector<BitSet> configs(M); for (int m = 0; m < M; ++m) { configs[m].reset(); for (int i = 0; i < N; ++i) { string s; cin >> s; for (int j = 0; j < N; ++j) { if (s[j] == '#') { int pos = i * N + j; configs[m].set(pos); } } } } // Process all pairs i < j for (int i = 0; i < M; ++i) { for (int j = i+1; j < M; ++j) { BitSet delta = configs[i] ^ configs[j]; bool ok = is_in_span(delta); if (i == 0 && j == 1) { cout << (ok ? "1" : "0"); } else if (i == 0 && j >= 2) { cout << (ok ? "1" : "0"); } else if (i == 1 && j == 2) { cout << (ok ? "1" : "0"); } else { cout << (ok ? "1" : "0"); } } if (i < M-1) cout << "\n"; } return 0; }