結果
問題 | No.228 ゆきこちゃんの 15 パズル |
ユーザー |
![]() |
提出日時 | 2015-08-04 08:48:41 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,326 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 165,024 KB |
実行使用メモリ | 6,812 KB |
最終ジャッジ日時 | 2024-07-18 01:12:23 |
合計ジャッジ時間 | 2,133 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 WA * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> long long inversion_number(const vector<T>& v) { function<long long(vector<T>&)> f = [&](vector<T>& v){ if (v.size() <= 1u) return 0; int n = v.size(); vector<int> a(v.begin(), v.begin() + n / 2); vector<int> b(v.begin() + n / 2, v.end()); int count = f(a) + f(b); for (int i = 0, j = 0, k = 0; i < n; ++i) { if (k == b.size()) { v[i] = a[j++]; } else if (j == a.size()) { v[i] = b[k++]; } else if (a[j] <= b[k]) { v[i] = a[j++]; } else { v[i] = b[k++]; count += n / 2 - j; } } return count; }; auto vv = v; return f(vv); } int main() { int a[4][4]; for (auto& i : a) { for (int& j : i) cin >> j; } vector<int> v; for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { int k = a[i][i % 2 ? j : 3 - j]; if (k) v.emplace_back(k); } } if (inversion_number(v) % 2) { cout << "No" << endl; return 0; } for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { if (a[i][j] == 0) continue; int d = a[i][j] - (i * 4 + j + 1); if (d != -4 && d != -1 && d != 0 && d != 1 && d != 4) { cout << "No" << endl; return 0; } } } cout << "Yes" << endl; }