結果

問題 No.2382 Amidakuji M
ユーザー nocturnal_1202nocturnal_1202
提出日時 2023-07-14 21:53:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 2,702 bytes
コンパイル時間 1,198 ms
コンパイル使用メモリ 125,864 KB
実行使用メモリ 5,504 KB
最終ジャッジ日時 2024-09-16 06:50:54
合計ジャッジ時間 2,634 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <complex>
#include <cassert>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <math.h>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include<regex>
#include<atcoder/modint>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,x) for(ll i=0;i<(ll)(x);i++)
#define rrep(i,x) for(ll i=1;i<=(ll)(x);i++)
#define all(v) v.begin(),v.end()
typedef pair<int, int> pii;
ll mod998 = 998244353;
ll mod109 = 1e9 + 7;
//vector<vector<int>> a(n,vector<int>(n));

using mint = atcoder::modint998244353;

struct BIT {
    vector<int> data;

    BIT(ll sz) {
        data.assign(++sz, 0);
    }

    // sum of [0,k]
    ll sum(ll k) {
        ll ret = 0;
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }

    // [i, j]
    ll range_sum(ll i, ll j) {
        if (i == 0) {
            return sum(j);
        }
        else {
            return sum(j) - sum(i - 1);
        }
    }

    void add(ll k, ll x) {
        for (++k; k < data.size(); k += k & -k) data[k] += x;
    }
};

// BITを用いた転倒数
// 
// (Aの値域に注意, 必要なら座標圧縮する)
// 入力：{100,100}などはREします
// ... というのはBITの値域が0~N-1なため。BIT(N)のNを直接指定するならRE回避可能
ll inversion_number(vector<int> A) {
    ll N = A.size();
    auto bit = BIT(N);
    ll cnt = 0;
    for(int i =0;i<N;i++) {
        ll a = A[i];
        ll num = i - bit.sum(a); // aより先に出現した、aよりも大きい数の個数
        // a以下の数をスルーするためにbit.sum(a)で引いている
        cnt += num;
        bit.add(a, 1);
    }
    return cnt;
}

int main(){

    int n;
    cin >> n;
    vector<int> a(n);
    ll m;
    cin >> m;
    rep(i, n) {
        cin >> a[i]; a[i]--;
    }
    ll k = inversion_number(a);
    if (k % m == 0)cout << k << endl;
    else {
        if (m % 2 == 0) {
            if (k % 2 == 1)cout << -1 << endl;
            else {
                cout << (k / m + 1) * m << endl;
            }
        }
        else if (((k / m + 1) * m) % 2 != k % 2) {
            cout << (k / m + 2) * m << endl;
        }
        else cout << (k / m + 1) * m << endl;
    }

}
0