結果
問題 | No.1078 I love Matrix Construction |
ユーザー |
![]() |
提出日時 | 2020-06-12 22:50:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,724 bytes |
コンパイル時間 | 3,254 ms |
コンパイル使用メモリ | 204,200 KB |
最終ジャッジ日時 | 2025-01-11 02:49:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 5 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define INF 1000000000 #define mod 1000000007 using ll=long long; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} // 可能なら出ていくのがないところからテキトーに構築して終わる. struct UnionFind{ vector<int> par; vector<int> siz; int c;//親の個数(グループ数) void init(int n){ c=n; for(int i=0;i<n;i++){ par.push_back(i); siz.push_back(1); } } UnionFind(int n){ init(n); } int root(int x){ //根を返す return(par[x]==x?x:(par[x]=root(par[x]))); } bool sameParent(int x,int y){ return(root(x)==root(y)); } void unite(int x, int y){ x=root(x);y=root(y); if(x==y) return; if(siz[x]<siz[y]) swap(x,y); siz[x] += siz[y];par[y]=x;c--; } int size(int x){ return siz[root(x)]; } }; signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n;cin>>n; auto get=[&](int i,int j,bool on=false){ int ret=i*n+j; if(on) ret+=n*n; return ret; }; UnionFind uf(2*n*n); vector<vector<int>> g(2*n*n); vector<int> s(n),t(n),u(n); rep(i,n) cin>>s[i]; rep(i,n) cin>>t[i]; rep(i,n) cin>>u[i]; rep(i,n) s[i]--,t[i]--; rep(i,n){ if(u[i]==0){ rep(j,n){ // s=1->t=0 // t=1->s=0 g[get(s[i],j,1)].push_back(get(j,t[i])); g[get(j,t[i],1)].push_back(get(s[i],j)); } }if(u[i]==1){ rep(j,n){ // s=1->t=1 // t=0->s=0 g[get(s[i],j,1)].push_back(get(j,t[i],1)); g[get(j,t[i])].push_back(get(s[i],j)); } }if(u[i]==2){ rep(j,n){ // s=0->t=0 // t=1->s=1 g[get(s[i],j)].push_back(get(j,t[i])); g[get(j,t[i],1)].push_back(get(s[i],j,1)); } }if(u[i]==3){ rep(j,n){ // s=0->t=1 // t=0->s=1 g[get(s[i],j)].push_back(get(j,t[i],1)); g[get(j,t[i])].push_back(get(s[i],j,1)); } } } vector<bool> check(2*n*n,false); function<bool(int)> dfs=[&](int now){ for(auto to:g[now]){ int ot; if(to>=n*n) ot=to-n*n; else ot=to; if(check[ot]){ return false; } if(check[to]) continue; check[to]=true; if(!dfs(to)){ check[now]=false; return false; } } return true; }; rep(i,n){ rep(j,n){ if(check[get(i,j)] or check[get(i,j,1)]) continue; auto res=dfs(get(i,j)); if(res) continue; res|=dfs(get(i,j,1)); if(!res){ cout<<-1<<endl; return 0; } } } rep(i,n){ rep(j,n){ if(!check[get(i,j)] and !check[get(i,j,1)]) cout<<0<<(j+1==n?"\n":" "); if(check[get(i,j)]) cout<<0<<(j+1==n?"\n":" "); if(check[get(i,j,1)]) cout<<1<<(j+1==n?"\n":" "); } } return 0; }