結果
問題 | No.2382 Amidakuji M |
ユーザー |
![]() |
提出日時 | 2023-07-14 21:58:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 4,271 bytes |
コンパイル時間 | 7,070 ms |
コンパイル使用メモリ | 360,592 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-16 06:57:15 |
合計ジャッジ時間 | 7,645 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#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);}}}}