結果
問題 | No.2382 Amidakuji M |
ユーザー |
![]() |
提出日時 | 2023-07-20 17:19:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 1,192 bytes |
コンパイル時間 | 2,315 ms |
コンパイル使用メモリ | 196,624 KB |
最終ジャッジ日時 | 2025-02-15 15:55:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> struct BIT { vector<T> bit; int N; BIT (int n){ N = n; bit.resize(N); } void add(int loc, T val){ loc++; while(loc <= N){ bit[loc-1] += val; loc += loc & -loc; } } T sum(int l, int r){ T res = _sum(r) - _sum(l-1); return res; } T _sum(int r){ r++; T res = 0; while(r > 0){ res += bit[r-1]; r -= r & -r; } return res; } }; ll inversion_number(vector<ll> &A){ ll d=0, mx=0; for (int i=0; i<A.size(); i++) mx = max(mx, A[i]); BIT<ll> tree(mx+1); for (int i=0; i<A.size(); i++){ d += tree.sum(A[i]+1, mx); tree.add(A[i], 1); } return d; } int main(){ ll N, M, I, K; cin >> N >> M; vector<ll> A(N); for (int i=0; i<N; i++) cin >> A[i]; I = inversion_number(A); K = (I+M-1)/M; for (ll i=K; i<=K+1; i++){ if ((M*i-I) % 2 == 0){ cout << M*i << endl; return 0; } } cout << -1 << endl; return 0; }