結果
問題 |
No.3131 Twin Slide Puzzles
|
ユーザー |
|
提出日時 | 2025-04-26 02:25:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,850 bytes |
コンパイル時間 | 2,622 ms |
コンパイル使用メモリ | 214,200 KB |
実行使用メモリ | 27,264 KB |
最終ジャッジ日時 | 2025-04-26 02:25:33 |
合計ジャッジ時間 | 15,375 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 17 WA * 40 |
ソースコード
#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; 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; } } }