結果
問題 | No.2505 matriX cOnstRuction |
ユーザー |
![]() |
提出日時 | 2023-10-13 23:35:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,112 ms / 2,500 ms |
コード長 | 2,998 bytes |
コンパイル時間 | 2,223 ms |
コンパイル使用メモリ | 211,236 KB |
最終ジャッジ日時 | 2025-02-17 07:36:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 64 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1000000;const long long INF2 = 1000000000000;int main(){int T;cin >> T;for (int i = 0; i < T; i++){int n, m;cin >> n >> m;vector<int> R(n);for (int j = 0; j < n; j++){cin >> R[j];}vector<int> C(m);for (int j = 0; j < m; j++){cin >> C[j];}vector<vector<int>> a(n, vector<int>(m));for (int j = 0; j < n; j++){for (int k = 0; k < m; k++){cin >> a[j][k];}}bool ok = true;for (int j = 0; j < n - 1; j++){for (int k = 0; k < m - 1; k++){if ((a[j][k] ^ a[j][k + 1] ^ a[j + 1][k] ^ a[j + 1][k + 1]) != 0){ok = false;}}}if (!ok){cout << -1 << endl;} else {vector<int> A(n + m);for (int j = 0; j < n; j++){A[j] = R[j];}for (int j = 0; j < m; j++){A[n + j] = C[j];}vector<int> B(n + m);B[0] = 0;for (int j = 1; j < n; j++){B[j] = B[0] ^ a[0][0] ^ a[j][0];}for (int j = 0; j < m; j++){B[n + j] = B[0] ^ a[0][j];}vector<int> A2(n + m);for (int j = 0; j < n + m; j++){if (A[j] == 0){A2[j] = 0;} else {int p = 32 - __builtin_clz(A[j]);A2[j] = (1 << p) - 1;}}vector<pair<int, int>> query;auto add = [&](int b, int mn, int add){int curr = 0;for (int j = 29; j >= 0; j--){if ((mn >> j & 1) == 0){if ((b >> j & 1) == 0){query.push_back(make_pair(curr + (1 << j), add));query.push_back(make_pair(curr + (1 << j) * 2, -add));} else {query.push_back(make_pair(curr, add));query.push_back(make_pair(curr + (1 << j), -add));curr |= 1 << j;}} else {if ((b >> j & 1) == 0){curr |= 1 << j;}}}};for (int j = 0; j < n + m; j++){add(B[j], 0, 1);add(B[j], A[j], 1);add(B[j], A2[j], INF);}query.push_back(make_pair(0, 0));query.push_back(make_pair(1 << 30, 0));int cnt = query.size();vector<int> X;for (int j = 0; j < cnt; j++){X.push_back(query[j].first);}sort(X.begin(), X.end());X.erase(unique(X.begin(), X.end()), X.end());int cnt2 = X.size();vector<long long> imos(cnt2, 0);for (int j = 0; j < cnt; j++){int p = lower_bound(X.begin(), X.end(), query[j].first) - X.begin();imos[p] += query[j].second;}for (int j = 1; j < cnt2; j++){imos[j] += imos[j - 1];}long long ans = INF2;for (int j = 0; j < cnt2 - 1; j++){ans = min(ans, imos[j]);}if (ans > INF){cout << -1 << endl;} else {cout << ans << endl;}}}}