結果
問題 | No.2382 Amidakuji M |
ユーザー | zer0-star |
提出日時 | 2023-07-14 21:50:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 3,230 bytes |
コンパイル時間 | 6,032 ms |
コンパイル使用メモリ | 317,364 KB |
実行使用メモリ | 7,652 KB |
最終ジャッジ日時 | 2023-10-14 11:56:41 |
合計ジャッジ時間 | 7,481 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,372 KB |
testcase_01 | AC | 1 ms
4,372 KB |
testcase_02 | AC | 2 ms
4,372 KB |
testcase_03 | AC | 20 ms
5,148 KB |
testcase_04 | AC | 36 ms
6,752 KB |
testcase_05 | AC | 6 ms
4,368 KB |
testcase_06 | AC | 22 ms
5,308 KB |
testcase_07 | AC | 14 ms
4,368 KB |
testcase_08 | AC | 2 ms
4,372 KB |
testcase_09 | AC | 31 ms
5,716 KB |
testcase_10 | AC | 44 ms
7,296 KB |
testcase_11 | AC | 16 ms
4,892 KB |
testcase_12 | AC | 31 ms
5,620 KB |
testcase_13 | AC | 2 ms
4,368 KB |
testcase_14 | AC | 2 ms
4,368 KB |
testcase_15 | AC | 1 ms
4,372 KB |
testcase_16 | AC | 1 ms
4,368 KB |
testcase_17 | AC | 2 ms
4,368 KB |
testcase_18 | AC | 2 ms
4,372 KB |
testcase_19 | AC | 50 ms
7,652 KB |
testcase_20 | AC | 48 ms
7,524 KB |
testcase_21 | AC | 49 ms
7,476 KB |
ソースコード
#include <bits/extc++.h> #include <atcoder/all> #ifdef ONLINE_JUDGE #include <bits/extc++.h> #include <atcoder/all> #else // #include "all.h" #endif using 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; }