結果
問題 | No.2382 Amidakuji M |
ユーザー |
|
提出日時 | 2023-07-14 21:50:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 3,230 bytes |
コンパイル時間 | 6,821 ms |
コンパイル使用メモリ | 307,248 KB |
最終ジャッジ日時 | 2025-02-15 13:56:39 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/extc++.h>#include <atcoder/all>#ifdef ONLINE_JUDGE#include <bits/extc++.h>#include <atcoder/all>#else// #include "all.h"#endifusing ll = long long int;template <class T>bool chmin(T &x, const T val) {if (x > val) {x = val;return true;} else {return false;}}template <class T>bool chmax(T &x, const T val) {if (x < val) {x = val;return true;} else {return false;}}template <class T, class U>std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {return is >> p.first >> p.second;}template <class T>std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (T &x : v) is >> x;return is;}template <class... T>std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) {[&is, &tpl ]<size_t... I>(std::index_sequence<I...>) {(is >> ... >> std::get<I>(tpl));}(std::make_index_sequence<std::tuple_size_v<std::tuple<T...>>>{});return is;}template <class T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {for (int i = 0; i < v.size(); i++)os << v[i] << (i == v.size() - 1 ? "" : " ");return os;}struct Initialization {Initialization() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);}} initialization;constexpr std::pair<int, int> dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};template <typename T>using infs = std::numeric_limits<T>;template <typename T>class factorials {size_t n;std::vector<T> fact, inv_fact;void extend(size_t m) {if (m <= n) return;fact.resize(m + 1);inv_fact.resize(m + 1);for (size_t i = n + 1; i <= m; i++) fact[i] = fact[i - 1] * i;inv_fact[m] = fact[m].inv();for (size_t i = m - 1; i >= n + 1; i--) inv_fact[i] = inv_fact[i + 1] * i;n = m;}public:factorials() : n(0), fact(1, 1), inv_fact(1, 1) {}factorials(size_t n) : n(n), fact(n + 1), inv_fact(n + 1) {fact[0] = 1;for (size_t i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;inv_fact[n] = fact[n].inv();for (size_t i = n; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i;}T inv(int k) {extend(k);return inv_fact[k];}T operator()(int k) {extend(k);return fact[k];}T perm(int n, int k) {if (n < k) return 0;if (k < 0) return 0;extend(n);return fact[n] * inv_fact[n - k];}T comb(int n, int k) {if (n < k) return 0;if (k < 0) return 0;extend(n);return fact[n] * inv_fact[n - k] * inv_fact[k];}};template <typename T>class fps {std::vector<T> v;public:fps(int n) : v(n) {}fps(std::vector<T> v) : v(v) {}};using mint = atcoder::modint998244353;int op(int a, int b) { return a + b; }int e() { return 0; }int main() {int n;ll m;std::cin >> n >> m;std::vector<ll> a(n);std::cin >> a;atcoder::segtree<int, op, e> seg(n);ll tento = 0;for (int i = 0; i < n; i++) {tento += seg.prod(a[i], n);seg.set(a[i] - 1, 1);}ll k = (tento + m - 1) / m * m;if (tento % 2 == 1 && m % 2 == 0) {std::cout << -1 << std::endl;return 0;}if (tento % 2 != k % 2) {k += m;}std::cout << k << std::endl;}