結果

問題 No.2991 Hypercubic Graph Flow
コンテスト
ユーザー umezo
提出日時 2024-12-16 10:12:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 2,553 bytes
コンパイル時間 3,141 ms
コンパイル使用メモリ 256,756 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-12-16 10:12:31
合計ジャッジ時間 4,612 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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;
  }
  
  if(n%2==0){
    auto A=f(f,n);
    int N=(1<<n);
    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;
        }
      }
    }
    cout<<"Yes\n";
    rep(i,N){
      rep(j,N){
        if(j) cout<<" ";
        cout<<A[i][j];
      }
      cout<<'\n';
    }
  }
  else{
    n--;
    auto A=f(f,n);
    int N=(1<<n);
    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;
        }
      }
    }
    set<int> s;
    rep(i,N) rep(j,N){
      if(A[i][j]!=0 && !s.count(j)){
        A[i][j]*=2;
        s.insert(j);
        break;
      }
    }
    n++;
    auto B=f(f,n);
    N=(1<<n);
    rep(i,N/2) rep(j,N/2){
      B[i][j]=A[i][j];
      B[i+N/2][j+N/2]=-B[i][j];
    }
    rep(i,N/2){
      int cnt=0;
      rep(j,N){
        if(j<N/2) cnt+=B[i][j];
        if(j>=N/2 && B[i][j]==X){
          B[i][j]=-cnt;
          B[i+N/2][j-N/2]=cnt;
        }
      }
    }
    cout<<"Yes\n";
    rep(i,N){
      rep(j,N){
        if(j) cout<<" ";
        cout<<B[i][j];
      }
      cout<<'\n';
    }
  }
    
  return 0;
}
0