結果

問題 No.283 スライドパズルと魔方陣
ユーザー anta
提出日時 2015-09-27 21:34:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,477 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 95,168 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-26 06:34:45
合計ジャッジ時間 5,637 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:133:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  133 |                         scanf("%d", &A[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
void oddMagicSquare(int N, vector<vi> &a) {
    int i = 0, j = N / 2;
    a.assign(N, vi(N));
    int sqr = N * N;
    rer(k, 1, sqr) {
        a[i][j] = k;
        -- i, ++ j;
        if(k % N == 0) {
            i += 2;
            -- j;
        }else {
            if(j == N) {
                j -= N;
            }else if(i < 0) {
                i += N;
            }
        }
    }
}
void magicSquare(int N, vector<vi> &a) {
    if(N % 2 == 1) {
        oddMagicSquare(N, a);
    }else if(N % 4 == 0) {
        a.assign(N, vi(N));
        vector<vi> I(N, vi(N, 0)), J = I;
        int k = 1;
        rep(i, N) rep(j, N)
            a[i][j] = k ++;
        rep(i, N) rep(j, N) if((i + 1) % 4 / 2 == (j + 1) % 4 / 2)
            a[i][j] = N * N + 1 - a[i][j];
    }else {
        a.assign(N, vi(N));
        int p = N / 2, pp = p * p;
        vector<vi> M;
        oddMagicSquare(p, M);
        rep(i, p) rep(j, p) {
            a[i][j] = M[i][j];
            a[i+p][j] = M[i][j] + 3*pp;
            a[i][j+p] = M[i][j] + 2*pp;
            a[i+p][j+p] = M[i][j] + pp;
        }
        vi I(p, 0), J;
        rep(i, p) I[i] = i+1;
        int k = (N - 2) / 4;
        rep(i, k) J.push_back(i);
        reu(i, N - k + 1, N) J.push_back(i);
        rep(i, p) rep(j, J.size())
            swap(a[i][J[j]], a[i+p][J[j]]);
        swap(a[k][0], a[k+p][0]);
        swap(a[k][k], a[k+p][k]);
    }
}
bool getParity(const vector<int> &perm) {
    int n = perm.size();
    vector<bool> vis(n);
    bool p = false;
    rep(i, n) if(!vis[i]) {
        int j = i;
        int len = 0;
        while(!vis[j]) {
            vis[j] = true;
            j = perm[j];
            ++ len;
        }
        if(len % 2 == 0)
            p = !p;
    }
    return p;
}
//Aは[1..h*w]
bool getSlidingParity(const vector<vi> &A) {
    int h = A.size(), w = A[0].size();
    vi perm(h * w);
    int dist = 0;
    rep(i, h) rep(j, w) {
        perm[A[i][j] - 1] = i * w + j;
        if(A[i][j] == h * w)
            dist += abs(h - 1 - i) + abs(w - 1 - j);
    }
    bool p = getParity(perm);
    bool q = dist % 2 != 0;
    return p != q;
}
int main() {
    int N;
    while(cin >> N) {
        vector<vi> A(N, vi(N));
        rep(i, N) rep(j, N) {
            scanf("%d", &A[i][j]);
            if(A[i][j] == 0)
                A[i][j] = N * N;
        }
        if(N == 2) {
            puts("impossible");
            continue;
        }
        bool parityA = getSlidingParity(A);
        vector<vi> org;
        magicSquare(N, org);
        vector<vi> board = org;
        if(getSlidingParity(board) != parityA) {
            if(N % 2 == 0) {
                reverse(all(board));
            } else {
                board[0].swap(board[N-1]);
            }
        }
        puts("possible");
        rep(i, N) {
            rep(j, N) {
                if(j != 0)
                    putchar(' ');
                printf("%d", board[i][j]);
            }
            puts("");
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
2