結果
問題 |
No.2382 Amidakuji M
|
ユーザー |
![]() |
提出日時 | 2023-07-15 13:27:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 982 bytes |
コンパイル時間 | 736 ms |
コンパイル使用メモリ | 73,852 KB |
最終ジャッジ日時 | 2025-02-15 14:58:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream> using namespace std; #include <vector> #include <cassert> template<typename T> struct BIT{//0-indexed private: std::vector<T> data; const int n; public: BIT(int sz) : data(sz+1,0), n(sz) {} T sum(size_t i) const noexcept {//sum[0,i) //++i; T s = 0; while(i > 0){ s += data[i]; i -= i&(-i); } return s; } T sum(size_t i, size_t j) const noexcept {// sum[i,j) return sum(j) - sum(i); } void add(int i, T x) noexcept { ++i; assert(i > 0); while(i <= n){ data[i] += x; i += i&(-i); } } }; int main(){ int n; long long m; cin >> n >> m; vector<int> P(n); for(int i = 0; i < n; ++i){ cin >> P[i]; --P[i]; } BIT<long long> bit(n); long long r = 0; for(auto p: P){ r += bit.sum(p,n); bit.add(p,1); } long long ans = (r+m-1)/m*m; if((ans-r)%2) ans += m; if((ans-r)%2){ cout << -1 << '\n'; return 0; } cout << ans << '\n'; }