結果
問題 | No.2382 Amidakuji M |
ユーザー | haihamabossu |
提出日時 | 2023-07-14 23:18:19 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 5,017 bytes |
コンパイル時間 | 3,954 ms |
コンパイル使用メモリ | 153,572 KB |
実行使用メモリ | 15,436 KB |
最終ジャッジ日時 | 2023-10-14 13:47:00 |
合計ジャッジ時間 | 3,383 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,372 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 14 ms
7,272 KB |
testcase_04 | AC | 22 ms
11,188 KB |
testcase_05 | AC | 4 ms
4,348 KB |
testcase_06 | AC | 15 ms
7,576 KB |
testcase_07 | AC | 9 ms
5,488 KB |
testcase_08 | AC | 1 ms
4,352 KB |
testcase_09 | AC | 19 ms
9,884 KB |
testcase_10 | AC | 29 ms
14,680 KB |
testcase_11 | AC | 10 ms
6,268 KB |
testcase_12 | AC | 19 ms
9,924 KB |
testcase_13 | AC | 0 ms
4,348 KB |
testcase_14 | AC | 1 ms
4,348 KB |
testcase_15 | AC | 1 ms
4,356 KB |
testcase_16 | AC | 1 ms
4,356 KB |
testcase_17 | AC | 1 ms
4,352 KB |
testcase_18 | AC | 1 ms
4,352 KB |
testcase_19 | AC | 34 ms
15,436 KB |
testcase_20 | AC | 32 ms
14,296 KB |
testcase_21 | AC | 33 ms
14,308 KB |
ソースコード
//https://github.com/rust-lang-ja/ac-library-rs pub mod fenwicktree { use std::ops::{Bound, RangeBounds}; // Reference: https://en.wikipedia.org/wiki/Fenwick_tree pub struct FenwickTree<T> { n: usize, ary: Vec<T>, e: T, } impl<T: Clone + std::ops::AddAssign<T>> FenwickTree<T> { pub fn new(n: usize, e: T) -> Self { FenwickTree { n, ary: vec![e.clone(); n], e, } } pub fn accum(&self, mut idx: usize) -> T { let mut sum = self.e.clone(); while idx > 0 { sum += self.ary[idx - 1].clone(); idx &= idx - 1; } sum } /// performs data[idx] += val; pub fn add<U: Clone>(&mut self, mut idx: usize, val: U) where T: std::ops::AddAssign<U>, { let n = self.n; idx += 1; while idx <= n { self.ary[idx - 1] += val.clone(); idx += idx & idx.wrapping_neg(); } } /// Returns data[l] + ... + data[r - 1]. pub fn sum<R>(&self, range: R) -> T where T: std::ops::Sub<Output = T>, R: RangeBounds<usize>, { let r = match range.end_bound() { Bound::Included(r) => r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => l + 1, Bound::Unbounded => return self.accum(r), }; self.accum(r) - self.accum(l) } } #[cfg(test)] mod tests { use super::*; use std::ops::Bound::*; #[test] fn fenwick_tree_works() { let mut bit = FenwickTree::new(5, 0i64); // [1, 2, 3, 4, 5] for i in 0..5 { bit.add(i, i as i64 + 1); } assert_eq!(bit.sum(0..5), 15); assert_eq!(bit.sum(0..4), 10); assert_eq!(bit.sum(1..3), 5); assert_eq!(bit.sum(..), 15); assert_eq!(bit.sum(..2), 3); assert_eq!(bit.sum(..=2), 6); assert_eq!(bit.sum(1..), 14); assert_eq!(bit.sum(1..=3), 9); assert_eq!(bit.sum((Excluded(0), Included(2))), 5); } } } use fenwicktree::*; pub mod binary_search { type T = usize; pub fn binary_search(mut ok: T, mut ng: T, f: impl Fn(T) -> bool) -> T { let cont = |ok: T, ng: T| { let l = ok.min(ng); let r = ok.max(ng); l + 1 < r }; while cont(ok, ng) { let x = (ok + ng) / 2; if f(x) { ok = x; } else { ng = x; } } ok } } pub mod scanner { pub struct Scanner { buf: Vec<String>, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next<T: std::str::FromStr>(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec<String> { source .split_whitespace() .rev() .map(String::from) .collect::<Vec<_>>() } } } use crate::FenwickTree; use crate::{binary_search::binary_search, scanner::Scanner}; use std::io::Write; fn main() { let mut scanner = Scanner::new(); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let t: usize = 1; for _ in 0..t { solve(&mut scanner, &mut out); } } fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) { let n: usize = scanner.next(); let m: usize = scanner.next(); let p = (0..n) .map(|_| scanner.next::<usize>() - 1) .collect::<Vec<_>>(); let mut count = 0usize; let mut bit = FenwickTree::new(n, 0usize); for i in 0..n { count += p[i] - bit.sum(0..p[i]); bit.add(p[i], 1); } if count == 0 { writeln!(out, "0").unwrap(); return; } if m % 2 == 0 && count % 2 == 1 { writeln!(out, "-1").unwrap(); return; } let mut x = binary_search(2e18 as usize / m, 0, |x| count <= x * m); if x * m % 2 != count % 2 { x += 1; } writeln!(out, "{}", x * m).unwrap(); }