結果
問題 | No.2505 matriX cOnstRuction |
ユーザー |
👑 ![]() |
提出日時 | 2023-10-17 03:25:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 622 ms / 2,500 ms |
コード長 | 1,717 bytes |
コンパイル時間 | 2,205 ms |
コンパイル使用メモリ | 212,528 KB |
最終ジャッジ日時 | 2025-02-17 08:07:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 64 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF=2100000000;#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}void solve();int main() {int t=1;cin>>t;rep(i,0,t) solve();}void solve(){int N,M;cin>>N>>M;vector<int> p(N),q(M);rep(i,0,N) cin>>p[i];rep(i,0,M) cin>>q[i];vector<vector<int>> A(N,vector<int>(M));rep(i,0,N) rep(j,0,M) cin>>A[i][j];vector<int> X(N),Y(M);Y=A[0];rep(i,0,N) X[i]=(A[i][0]^Y[0]);rep(i,0,N) rep(j,0,M){if(A[i][j]^X[i]^Y[j]){cout<<"-1\n";return;}}rep(i,0,M) p.push_back(q[i]),X.push_back(Y[i]);map<int,int> m;map<int,int> dp;rep(i,0,N+M){int tmp1=p[i],tmp2=X[i],tmp3=1;tmp1++;while(tmp3<tmp1) tmp3*=2;for(int d=29;d>=0;d--){if(tmp1&(1<<d)){int l=(((1<<30)-(1<<d))&(tmp1^tmp2^(1<<d)));int r=l+(1<<d);dp[l]--,dp[r]++;}if(tmp3&(1<<d)){int l=(((1<<30)-(1<<d))&(tmp3^tmp2^(1<<d)));int r=l+(1<<d);dp[l]+=2,dp[r]-=2;m[l]++,m[r]--;}}if(tmp1==(1<<30)) dp[0]--,dp[1<<30]++;if(tmp3==(1<<30)) dp[0]+=2,dp[1<<30]-=2,m[0]++,m[1<<30]--;dp[X[i]]--,dp[X[i]+1]++;}int ans=INF;int tmp=0;int v=0;for(auto x:dp){tmp+=m[x.first];v+=x.second;//cout<<x.first<<" "<<tmp<<" "<<v<<endl;if(tmp==N+M) chmin(ans,v);}if(ans!=INF) cout<<ans<<"\n";else cout<<"-1\n";}