結果

問題 No.2505 matriX cOnstRuction
ユーザー SSRSSSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0