結果

問題 No.283 スライドパズルと魔方陣
コンテスト
ユーザー tko919
提出日時 2020-12-23 22:01:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,734 bytes
コンパイル時間 1,797 ms
コンパイル使用メモリ 173,536 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 16:33:42
合計ジャッジ時間 6,094 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

typedef array<int,2> P;
typedef vector<vector<int>> VV;

VV magic(int n){
   VV res(n,vector<int>(n));
   if(n&1){
      int x=0,y=n/2,cur=1;
      rep(_,0,n*n){
         res[x][y]=cur++;
         int nx=(x-1+n)%n;
         int ny=(y+1)%n;
         if(res[nx][ny])x=(x+1)%n;
         else{swap(x,nx); swap(y,ny);}
      }
   }
   else if(n%4==0){
      rep(i,0,n)rep(j,0,n){
         int cur=i*n+j+1;
         if((i%4==1 or i%4==2)+(j%4==1 or j%4==2)==1){
            res[i][j]=n*n+1-cur;
         }
         else{
            res[i][j]=cur;
         }
      }
   }
   else{
      int m=n/2;
      auto sub=magic(m);
      for(auto& v:sub)for(auto& x:v)x=(x-1)*4;
      int add[3][2][2]={{{4,1},{2,3}},{{1,4},{2,3}},{{1,4},{3,2}}};
      rep(i,0,m)rep(j,0,m){
         int type;
         if(i<m/2)type=0;
         else if(i==m/2){
            if(j==m/2)type=1;
            else type=0;
         }
         else if(i==m/2+1){
            if(j==m/2)type=0;
            else type=1;
         }
         else type=2;
         rep(a,0,2)rep(b,0,2)res[i*2+a][j*2+b]=sub[i][j]+add[type][a][b];
      }
   }
   return res;
}

template<typename T>struct BIT{
   int n; T m=0; vector<T> val;
   BIT(int _n):n(_n),val(_n+10){}
   void clear(){val.assign(n+10,0); m=0;}
   void add(int i,T x){
      for(i++;i<=n;i+=(i&-i))val[i]+=x;
      m+=x;
   }
   T sum(int i){
      T res=0;
      for(i++;i;i-=(i&-i))res+=val[i];
      return res;
   }
};

bool parity(const VV& g){
   int n=g.size();
   vector<int> a(n*n);
   rep(i,0,n)rep(j,0,n)a[i*n+j]=g[i][j];
   BIT<int> bit(n*n+10);
   int res=0;
   rep(i,0,n*n){
      res+=bit.m-bit.sum(a[i]);
      bit.add(a[i],1);
   }
   rep(i,0,n*n)if(a[i]==n*n){
      res+=(n-1-(i/n))+(n-1-(i%n));
   }
   return res&1;
}

int main(){
   int n; cin>>n;
   VV a(n,vector<int>(n));
   rep(i,0,n)rep(j,0,n){
      cin>>a[i][j];
      if(a[i][j]==0)a[i][j]=n*n;
   }
   if(n==2){
      puts("impossible");
      return 0;
   }
   puts("possible");
   auto target=magic(n);
   bool f=parity(a),g=parity(target);
   if(f+g==1){
      if(n%4==1)rep(i,0,n)swap(target[i][0],target[i][n-1]);
      else rep(i,0,n)rep(j,0,n/2)swap(target[i][j],target[i][n-1-j]);
   }
   rep(i,0,n){
      rep(j,0,n)cout<<target[i][j]<<(j==n-1?'\n':' ');
   }
   return 0;
}
0