結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | akakimidori |
提出日時 | 2024-03-08 21:56:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 4,292 bytes |
コンパイル時間 | 13,648 ms |
コンパイル使用メモリ | 383,340 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2024-09-29 19:36:07 |
合計ジャッジ時間 | 16,689 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
コンパイルメッセージ
warning: type alias `Map` is never used --> src/main.rs:122:6 | 122 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:123:6 | 123 | type Set<T> = BTreeSet<T>; | ^^^
ソースコード
mod util {pub trait Join {fn join(self, sep: &str) -> String;}impl<T, I> Join for IwhereI: Iterator<Item = T>,T: std::fmt::Display,{fn join(self, sep: &str) -> String {let mut s = String::new();use std::fmt::*;for (i, v) in self.enumerate() {if i > 0 {write!(&mut s, "{}", sep).ok();}write!(&mut s, "{}", v).ok();}s}}}// 1-indexedなBIT// 座標xへの加算、[1,x]の和, ([1,x]の和)>=s となる最小のxの探索// ---------- begin fenwick tree ----------pub struct Fenwick<T> {zero: T,a: Box<[T]>,}impl<T> Fenwick<T>whereT: Copy + std::ops::Add<Output = T>,{pub fn new(size: usize, zero: T) -> Fenwick<T> {Fenwick {zero: zero,a: vec![zero; size + 1].into_boxed_slice(),}}pub fn init(&mut self) {for a in self.a.iter_mut() {*a = self.zero;}}pub fn add(&mut self, mut x: usize, v: T) {assert!(x > 0);while let Some(a) = self.a.get_mut(x) {*a = *a + v;x += x & (!x + 1);}}pub fn sum(&self, mut x: usize) -> T {assert!(x < self.a.len());let mut res = self.zero;while x > 0 {res = res + self.a[x];x -= x & (!x + 1);}res}}impl<T> Fenwick<T>whereT: Copy + std::ops::Add<Output = T> + PartialOrd,{pub fn search(&self, s: T) -> usize {debug_assert!(self.sum(self.a.len() - 1) >= s);let mut k = 1;while 2 * k < self.a.len() {k *= 2;}let mut x = 0;let mut w = self.zero;while k > 0 {self.a.get(x + k).map(|a| {if w + *a < s {w = w + *a;x += k;}});k >>= 1;}x + 1}}// ---------- end fenwick tree ----------// ---------- begin scannner ----------#[allow(dead_code)]mod scanner {use std::str::FromStr;pub struct Scanner<'a> {it: std::str::SplitWhitespace<'a>,}impl<'a> Scanner<'a> {pub fn new(s: &'a String) -> Scanner<'a> {Scanner {it: s.split_whitespace(),}}pub fn next<T: FromStr>(&mut self) -> T {self.it.next().unwrap().parse::<T>().ok().unwrap()}pub fn next_bytes(&mut self) -> Vec<u8> {self.it.next().unwrap().bytes().collect()}pub fn next_chars(&mut self) -> Vec<char> {self.it.next().unwrap().chars().collect()}pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {(0..len).map(|_| self.next()).collect()}}}// ---------- end scannner ----------use std::io::Write;use std::collections::*;type Map<K, V> = BTreeMap<K, V>;type Set<T> = BTreeSet<T>;type Deque<T> = VecDeque<T>;fn main() {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut sc = scanner::Scanner::new(&s);let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());run(&mut sc, &mut out);}fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {let t: u32 = sc.next();for _ in 0..t {let n: usize = sc.next();let p = sc.next_vec::<usize>(n);let mut deq = Deque::new();deq.push_back(p[0]);let mut bit = Fenwick::new(n, 0);bit.add(p[0], 1);let mut inv = 0usize;for (i, p) in p.iter().enumerate().skip(1) {let c = bit.sum(*p);bit.add(*p, 1);let mut front = c < i - c;front |= c == i - c && *p < deq[0];if front {inv += c;deq.push_front(*p);} else {inv += i - c;deq.push_back(*p);}}writeln!(out, "{}", inv).ok();use util::*;writeln!(out, "{}", deq.iter().join(" ")).ok();}}