結果
問題 | 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"; }