結果
問題 | No.2382 Amidakuji M |
ユーザー | random contestant |
提出日時 | 2023-07-14 22:15:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 2,170 bytes |
コンパイル時間 | 4,059 ms |
コンパイル使用メモリ | 266,196 KB |
実行使用メモリ | 18,584 KB |
最終ジャッジ日時 | 2023-10-14 12:28:43 |
合計ジャッジ時間 | 6,008 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,352 KB |
testcase_03 | AC | 38 ms
9,640 KB |
testcase_04 | AC | 66 ms
14,580 KB |
testcase_05 | AC | 11 ms
4,896 KB |
testcase_06 | AC | 41 ms
10,092 KB |
testcase_07 | AC | 24 ms
7,520 KB |
testcase_08 | AC | 3 ms
4,352 KB |
testcase_09 | AC | 59 ms
13,236 KB |
testcase_10 | AC | 87 ms
17,520 KB |
testcase_11 | AC | 29 ms
8,340 KB |
testcase_12 | AC | 60 ms
13,392 KB |
testcase_13 | AC | 1 ms
4,352 KB |
testcase_14 | AC | 2 ms
4,352 KB |
testcase_15 | AC | 2 ms
4,352 KB |
testcase_16 | AC | 1 ms
4,352 KB |
testcase_17 | AC | 1 ms
4,352 KB |
testcase_18 | AC | 1 ms
4,352 KB |
testcase_19 | AC | 91 ms
18,584 KB |
testcase_20 | AC | 90 ms
18,472 KB |
testcase_21 | AC | 95 ms
18,576 KB |
ソースコード
// #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; #define rep(i,n) for (ll i = 0; i < (n); ++i) using vl = vector<ll>; using vvl = vector<vl>; using P = pair<ll,ll>; #define pb push_back #define int long long #define double long double #define INF (ll) 3e18 // Ctrl + Shift + B コンパイル // Ctrl + C 中断 // ./m 実行 // 転倒数ライブラリ // from ARC 120 // vl a とvl b を渡すことで // vl a をvl b にするために必要なswap回数を出力する // 不可能な場合は その旨を文章に出力する // 不可能事の出力が必要な場合は // 文章の位置を return -1にすることで // 不可能判定が可能 template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; ll tentou(vl x, vl y) { ll n = x.size(); vector<pair<ll, ll>> a(n), b(n); for (ll i = 0; i < n; i++) { a[i].first = x[i]; a[i].second = i; } for (ll i = 0; i < n; i++) { b[i].first = y[i]; b[i].second = i; } sort(a.begin(), a.end()); sort(b.begin(), b.end()); vector<ll> p(n); for (ll i = 0; i < n; i++) { if (a[i].first != b[i].first) { cout << -1 << '\n'; cout << "swapにより配列 a b を等しくすることは不可能です" << endl; return 0; } p[a[i].second] = b[i].second; } fenwick<ll> fenw(n); ll ans = 0; for (ll i = n - 1; i >= 0; i--) { ans += fenw.get(p[i]); fenw.modify(p[i], 1); } return ans; } signed main(){ int n; cin >> n; int m; cin >> m; vl a(n); vl b(n); rep(i,n) cin >> a[i]; rep(i,n) b[i] = i+1; int tent = tentou(a, b); int k1 = tent / m * m; if (k1 < tent) k1 += m; int k2 = k1 + m; if (k1 % 2 == tent % 2) {cout << k1 << endl; return 0;} if (k2 % 2 == tent % 2) {cout << k2 << endl; return 0;} cout << -1 << endl; }