結果

問題 No.3131 Twin Slide Puzzles
コンテスト
ユーザー GOTKAKO
提出日時 2025-04-26 02:28:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,017 ms / 4,000 ms
コード長 2,918 bytes
コンパイル時間 2,152 ms
コンパイル使用メモリ 214,676 KB
実行使用メモリ 131,072 KB
最終ジャッジ日時 2025-06-20 02:52:24
合計ジャッジ時間 35,619 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

random_device rnd;
mt19937 mt(rnd());

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

    vector<int> name(300000);
    iota(name.begin(),name.end(),0);

    auto check = [&](int n,vector<int> P) -> bool {
        for(auto &p : P) p = name.at(p);

        int d1 = 0,d2 = 0;
        for(int i=0; i<n*n; i++){
            if(P.at(i)) continue;
            int x = i/n,y = i%n;
            d1 = (x+y)%2;
        }
        vector<bool> already(n*n);
        for(int i=0; i<n*n; i++){
            if(already.at(i)) continue;
            already.at(i) = true;
            int pos = P.at(i);
            while(pos != i) already.at(pos) = true,pos = P.at(pos),d2++;
        }
        return d1==(d2%2);
    };

    int N; cin >> N;
    vector<long long> A(N*N);
    for(auto &a : A) cin >> a;

    if(N <= 3){
        vector<int> P(N*N);
        iota(P.begin(),P.end(),0);
        map<long long,vector<int>> M;
        do{
            if(check(N,P) == false) continue;
            long long now = 0;
            for(int i=0; i<N*N; i++) now += A.at(i)*P.at(i);
            if(M.count(now)){
                cout << "Yes\n";
                for(int i=0; i<N*N; i++){
                    if(i%N) cout << " ";
                    cout << P.at(i);
                    if((i+1)%N == 0) cout << "\n";
                }
                P = M[now];
                for(int i=0; i<N*N; i++){
                    if(i%N) cout << " ";
                    cout << P.at(i);
                    if((i+1)%N == 0) cout << "\n";
                }
                return 0;
            }
            M[now] = P;
        }while(next_permutation(P.begin(),P.end()));
        cout << "No\n"; 
    }
    else{
        vector<int> P;
        for(int i=0; i<4; i++) for(int k=0; k<4; k++) name.at(i*N+k) = i*4+k,P.push_back(i*N+k);
        map<long long,vector<int>> M;
        while(true){
            shuffle(P.begin(),P.end(),mt);
            if(check(4,P) == false) continue;

            long long now = 0;
            for(int i=0; i<16; i++) now += A.at(i/4*N+i%4)*P.at(i);
            if(M.count(now)){
                cout << "Yes\n";
                for(int i=0; i<N; i++){
                    for(int k=0; k<N; k++){
                        if(k) cout << " ";
                        if(i < 4 && k < 4) cout << P.at(i*4+k);
                        else cout << i*N+k;
                    }
                    cout << "\n";
                }
                P = M[now];
                for(int i=0; i<N; i++){
                    for(int k=0; k<N; k++){
                        if(k) cout << " ";
                        if(i < 4 && k < 4) cout << P.at(i*4+k);
                        else cout << i*N+k;
                    }
                    cout << "\n";
                }
                return 0;
            }
            M[now] = P;
        }    
    }
}
0