結果
問題 | No.2382 Amidakuji M |
ユーザー | shirokami |
提出日時 | 2023-07-14 21:58:08 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 4,271 bytes |
コンパイル時間 | 5,418 ms |
コンパイル使用メモリ | 360,216 KB |
実行使用メモリ | 4,884 KB |
最終ジャッジ日時 | 2023-10-14 12:07:23 |
合計ジャッジ時間 | 6,597 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,352 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,352 KB |
testcase_03 | AC | 10 ms
4,348 KB |
testcase_04 | AC | 18 ms
4,348 KB |
testcase_05 | AC | 4 ms
4,348 KB |
testcase_06 | AC | 11 ms
4,348 KB |
testcase_07 | AC | 8 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,352 KB |
testcase_09 | AC | 16 ms
4,348 KB |
testcase_10 | AC | 23 ms
4,360 KB |
testcase_11 | AC | 10 ms
4,348 KB |
testcase_12 | AC | 17 ms
4,352 KB |
testcase_13 | AC | 1 ms
4,348 KB |
testcase_14 | AC | 1 ms
4,352 KB |
testcase_15 | AC | 1 ms
4,348 KB |
testcase_16 | AC | 1 ms
4,348 KB |
testcase_17 | AC | 1 ms
4,348 KB |
testcase_18 | AC | 1 ms
4,352 KB |
testcase_19 | AC | 24 ms
4,624 KB |
testcase_20 | AC | 24 ms
4,620 KB |
testcase_21 | AC | 25 ms
4,884 KB |
ソースコード
#include <bits/extc++.h> using namespace std; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // using namespace __gnu_pbds; // #include <boost/multiprecision/cpp_int.hpp> // using Bint = boost::multiprecision::cpp_int; #include <atcoder/all> using namespace atcoder; // https://atcoder.github.io/ac-library/production/document_ja/ typedef long long int ll; typedef long double ld; constexpr ll mod = 998244353; constexpr ll INF = 9'223'372'036'854'775'807/10; #define rep(i,n) for (ll i = 0; i < ll(n); ++i) #define All(a) (a).begin(),(a).end() #define Pi acos(-1) using V = vector<ll>; using P = pair<ll,ll>; vector<ll> dx = {1, 0, -1, 0, 1, 1, -1, -1}; vector<ll> dy = {0, 1, 0, -1, 1, -1, 1, -1}; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } struct Edge{ll to, cost;}; using Graph = vector<vector<Edge>>; struct IoSetup { IoSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << setprecision(15) << fixed; } } iosetup; void print(vector<string> &v) { for (string s : v) { cout << s << '\n'; } } template<typename T> void print(vector<pair<T, T>> &v, int w = 0) { for (int i = 0; i < (int)v.size(); i++) { cout << right << setw(w) << v[i].first << ' ' << v[i].second << '\n'; } } template<typename T> void print(vector<T> &v, int w = 0) { for (int i = 0; i < (int)v.size(); i++) { cout << right << setw(w) << v[i] << " \n"[i == (int)v.size() - 1]; } } template<typename T> void print(vector<vector<T>> &v, int w = 0) { for (int i = 0; i < (int)v.size(); i++) { print(v[i], w); } } template<typename T> void print(const T& arg) { cout << arg << '\n'; } template<typename T, typename... Args> void print(const T& arg, const Args&... args) { cout << arg << ' '; print(args...); } template<typename T> istream& operator>>(istream& is, vector<T>& vec) { for (auto& x : vec) is >> x; return is; } template<typename T> class BIT { private: int n; vector<T> bit; public: // 0_indexed で i 番目の要素に x を加える void add(int i, T x){ i++; while(i < n){ bit[i] += x, i += i & -i; } } // 0_indexed で [0,i] の要素の和(両閉区間!!) T sum(int i){ i++; T s = 0; while(i > 0){ s += bit[i], i -= i & -i; } return s; } BIT(){} //初期値がすべて0の場合 BIT(int sz) : n(sz+1), bit(n, 0){} BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){ for(int i = 0; i < n-1; i++){ add(i,v[i]); } } void print(){ for(int i = 0; i < n-1; i++){ cout << sum(i) - sum(i-1) << " "; } cout << "\n"; } //-1スタート void print_sum(){ for(int i = 0; i < n; i++){ cout << sum(i-1) << " "; } cout << "\n"; } }; // u を昇順にソートするのに必要な交換回数(転倒数) (u は {0,..., n-1} からなる重複を許した長さ n の数列) long long inv_count(const vector<int>& u) { int n = (int)u.size(); BIT<int> bt(n); long long ans = 0; for(int i = 0; i < n; i++){ ans += i - bt.sum(u[i]); bt.add(u[i], 1); } return ans; } // u を v に変換するのに必要な交換回数(転倒数) // (u, v は {0,..., n-1} からなる重複を許した長さ n の数列. ただし u, v 全体で各数字の個数は一致するものとする) long long inv_count(const vector<int>& u, const vector<int>& v) { int n = (int)u.size(); vector<vector<int> > p(n); BIT<int> bt(n); for(int i = n-1; i >= 0; --i){ p[u[i]].push_back(i); } long long ans = 0; for(int i = 0; i < n; ++i){ int pos = p[v[i]].back(); p[v[i]].pop_back(); ans += pos - bt.sum(pos); bt.add(pos, 1); } return ans; } int main() { ll n, m; cin >> n >> m; vector<int> p(n); cin >> p; rep(i, n) p[i]--; ll ic = inv_count(p); if (ic == 0) { print(0); return 0; } if (m%2 == 0) { if (ic%2 != 0) print(-1); else { print((m+ic-1)/m * m); } } else { if (ic%2 == 0) { print((2*m+ic-1)/(2*m) * 2*m); } else { if (ic <= m) { print(m); } else { ic -= m; print((2*m+ic-1)/(2*m) * 2*m + 1); } } } }