結果

問題 No.2991 Hypercubic Graph Flow
ユーザー umezo
提出日時 2024-12-16 09:45:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,368 bytes
コンパイル時間 3,315 ms
コンパイル使用メモリ 252,604 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-12-16 09:45:14
合計ジャッジ時間 4,814 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 9 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
template <class T> using V=vector<T>;
template <class T> using VV=V<V<T>>;

const int X=5;
 
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  auto f=[&](auto f,int n)->VV<int>{
    if(n==1){
      VV<int> A(2,V<int>(2));
      A[0][1]=X,A[1][0]=X;
      return A;
    }
    auto B=f(f,n-1);
    int N=(1<<n);
    VV<int> C(N,V<int>(N));
    rep(i,N/2) rep(j,N/2){
      C[i][j]=B[i][j];
      C[i+N/2][j+N/2]=B[i][j];
    }
    rep(i,N/2) C[i][i+N/2]=X;
    for(int i=N/2;i<N;i++) C[i][i-N/2]=X;
    return C;
  };
  
  
  int n;
  cin>>n;
  
  if(n==1){
    cout<<"No\n";
    return 0;
  }
  
  auto A=f(f,n);
  int N=(1<<n);
  
  if(n%2==0){
    int now=1;
    rep(i,N/2) rep(j,N/2){
      if(A[i][j]==X){
        A[i][j]=now;
        A[j][i]=-now;
        now*=-1;
        A[i+N/2][j+N/2]=-A[i][j];
      }
      else if(A[i][j]!=0){
        now=A[i][j];
        now*=-1;
        A[i+N/2][j+N/2]=-A[i][j];
      }
    }
    rep(i,N/2){
      int cnt=0;
      rep(j,N){
        if(j<N/2) cnt+=A[i][j];
        if(j>=N/2 && A[i][j]==X){
          A[i][j]=-cnt;
          A[j][i]=cnt;
        }
      }
    }
  }
  else{
    rep(i,N/2){
      int sum=0;
      rep(j,N/2){
        if(A[i][j]==X){
          if(sum==0){
            A[i][j]=1;
            A[j][i]=-1;
            sum++;
          }
          else if(sum==1){
            A[i][j]=1;
            A[j][i]=-1;
            sum++;
          }
          else if(sum>=2){
            A[i][j]=-1;
            A[j][i]=1;
            sum--;
          }
          else if(sum==-1){
            A[i][j]=-1;
            A[j][i]=1;
            sum--;
          }
          else if(sum<=-2){
            A[i][j]=1;
            A[j][i]=-1;
            sum++;
          }
          A[i+N/2][j+N/2]=-A[i][j];
        }
        else if(A[i][j]!=0){
          sum+=A[i][j];
          A[i+N/2][j+N/2]=-A[i][j];
        }
      }
    }
    rep(i,N/2){
      int cnt=0;
      rep(j,N){
        if(j<N/2) cnt+=A[i][j];
        if(j>=N/2 && A[i][j]==X){
          A[i][j]=-cnt;
          A[j][i]=cnt;
        }
      }
    }
  }
  cout<<"Yes\n";
  rep(i,N){
    rep(j,N){
      if(j) cout<<" ";
      cout<<A[i][j];
    }
    cout<<'\n';
  }
    
  return 0;
}
0