#1192030 (C++23(gcc16)) No.3739 Stronger Network

• 問題: No.3739 Stronger Network
• ユーザー: caz37OwO
• 提出日時: 2026-10-09 08:46:31
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 197 ms / 2,000 ms
• コード長: 3,562 bytes
• コンパイル時間: 6,446 ms
• コンパイル使用メモリ: 393,876 KB
• 実行使用メモリ: 19,152 KB
• 最終ジャッジ日時: 2026-10-09 08:46:44
• 合計ジャッジ時間: 13,097 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 48

ソースコード

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

using ll=long long;
using ldub=long double;
using lldub=__float128;
using str=string;

using mint=modint;

template<class T=ll>
using tup2=tuple<T,T>;
template<class T=ll>
using tup3=tuple<T,T,T>;
template<class T=ll>
using tup4=tuple<T,T,T,T>;
template<class T=ll>
using tup5=tuple<T,T,T,T,T>;
template<class T=ll>
using tup6=tuple<T,T,T,T,T,T>;
template<class T=ll>
using tup7=tuple<T,T,T,T,T,T,T>;

template<class T=ll>
using vec=vector<T>;
template<class T=ll>
using vec2=vector<vec<T>>;
template<class T=ll>
using vec3=vector<vec2<T>>;
template<class T=ll>
using vec4=vector<vec3<T>>;
template<class T=ll>
using vec5=vector<vec4<T>>;
template<class T=ll>
using vec6=vector<vec5<T>>;

template<class T>
using que=queue<T>;
template<class T>
using Pque=priority_queue<T>;
template<class T>
using pque=priority_queue<T, vector<T>, greater<T>>;

struct Edge{
  ll from,to,w=1,num=-1;
};
using gvec=vector<Edge>;
using gvec2=vector<gvec>;

template<class T>
bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define ins insert
#define tup make_tuple
#define low lower_bound
#define pops(a) __builtin_popcountll(a)
#define ctz(a) __builtin_ctzll(a)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define nperm(v) next_permutation(all(v))
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YN(f) cout << ((f)?"Yes":"No") << endl

const int IINF=2e9;
const ll INF=4e18;

#ifndef LOCAL
#define debug(x)
#endif




// =================================================




vec<ll> f(ll N){
  vec A;
  {
    ll n=N-1;
    A.pb(n);
    while(n){
      n^=(1<<ctz(n));
      A.pb(n);
    }
  }
  {
    ll s=0;
    for(ll k=20;k>=2;k--){
      if((((N-1)>>k)&1)==0) continue;
      ll n=s;
      vec B((1<<k)-1);
      for(ll i=0;i<(1<<k)-1;i++){
        n^=1<<ctz(i+1);
        B[i]=n;
      }
      for(ll i=0;i<(1<<k)-1;i++){
        ll f=0;
        f^=((B[i]>>1)&1)<<1;
        f^=((B[i]>>1)&1)<<(k-1);
        f^=((B[i]>>(k-1))&1)<<1;
        f^=((B[i]>>(k-1))&1)<<(k-1);
        B[i]^=f;
      }
      if((pops(s)+pops((N-1)>>2))&1) reverse(all(B));
      for(ll i=0;i<(1<<k)-1;i++) A.pb(B[i]);
      s^=1<<k;
    }
  }
  if((((N-1)>>1)&1)==1) A.pb(N-3);
  return A;
}

void solve(){
  ll N,M;
  cin >> N >> M;
  if((N&1)||(M&1)){
    cout << -1 << endl;
    return;
  }
  vec P=f(N);
  vec Q=f(M);
  vec2 dp(21,vec(21,INF));
  vec2 pre(21,vec(21));
  dp[20][20]=0;
  for(ll k=20;k>=0;k--){
    for(ll l=20;l>=0;l--){
      if(k!=20&&chmin(dp[k][l],(dp[k+1][l]<<1)+(((N-1)>>k)&1))) pre[k][l]=0;
      if(l!=20&&chmin(dp[k][l],(dp[k][l+1]<<1)+(((M-1)>>l)&1))) pre[k][l]=1;
    }
  }
  vec X(20),Y(20);
  {
    ll h=0,w=0;
    while(tup(h,w)!=tup(20,20)){
      if(pre[h][w]==0){
        X[h]=h+w;
        h++;
      }else{
        Y[w]=h+w;
        w++;
      }
    }
  }
  vec2 A(N,vec(M));
  for(ll i=0;i<N;i++){
    for(ll j=0;j<M;j++){
      ll v=0;
      for(ll k=0;k<20;k++) v+=((P[i]>>k)&1)<<X[k];
      for(ll l=0;l<20;l++) v+=((Q[j]>>l)&1)<<Y[l];
      A[i][j]=v;
    }
  }
  for(ll i=0;i<N;i++){
    for(ll j=0;j<M;j++) cout << A[i][j] << ' ';
    cout << endl;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  mint::set_mod(998244353);
  // mint::set_mod(1000000007);

  ll T=1;
  // cin >> T;
  while(T--) solve();
  return 0;
}