結果
問題 | No.576 E869120 and Rings |
ユーザー |
![]() |
提出日時 | 2018-05-21 18:42:38 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 829 ms / 1,500 ms |
コード長 | 4,899 bytes |
コンパイル時間 | 13,592 ms |
コンパイル使用メモリ | 379,032 KB |
実行使用メモリ | 35,248 KB |
最終ジャッジ日時 | 2024-06-28 15:32:05 |
合計ジャッジ時間 | 31,341 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
コンパイルメッセージ
warning: unused macro definition: `printf` --> src/main.rs:143:18 | 143 | macro_rules! printf { (arg:tt)*) => (write!(out, arg)*).unwrap()); } | ^^^^^^ | = note: `#[warn(unused_macros)]` on by default warning: method `unwrap` is never used --> src/main.rs:118:8 | 117 | impl<T: std::cmp::PartialOrd> Ordered<T> { | ---------------------------------------- method in this implementation 118 | fn unwrap(self) -> T { | ^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#[allow(dead_code)]fn getline() -> String {let mut res = String::new();std::io::stdin().read_line(&mut res).ok();res}#[allow(unused_macros)]macro_rules! readl {($t: ty) => {{let s = getline();s.trim().parse::<$t>().unwrap()}};($( $t: ty),+ ) => {{let s = getline();let mut iter = s.trim().split(' ');($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};}#[allow(unused_macros)]macro_rules! readlvec {($t:ty) => {{let s = getline();let iter = s.trim().split(' ');iter.map(|x| x.parse().unwrap()).collect::<Vec<$t>>()}};}#[allow(unused_macros)]// macro_rules! debug {// ($x:expr) => {// println!("{}: {:?}", stringify!($x), $x)// };// }macro_rules! debug { ($x: expr) => () }#[allow(dead_code)]fn show<T>(iter: T) -> StringwhereT: Iterator,T::Item: std::fmt::Display,{let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));res.pop();res}fn sliding_minimum<T>(a: &Vec<T>, width: usize) -> Vec<T>whereT: std::cmp::PartialOrd + Clone{let mut res = Vec::with_capacity(a.len() - width);let mut set = std::collections::VecDeque::new();for (i, e) in a.iter().enumerate().take(width) {while let Some((v, i)) = set.pop_back() {if v < e {set.push_back((v, i));break;}}set.push_back((e, i));}for (s, e) in a.iter().skip(width).enumerate() {res.push(set.front().expect("sliding_minimum error").0.clone());while let Some((v, i)) = set.pop_back() {if v < e {set.push_back((v, i));break;}}set.push_back((e, s + width));while let Some((v, i)) = set.pop_front() {if s + 1 <= i {set.push_front((v, i));break;}}}res.push(set.front().expect("sliding_minimum error").0.clone());res}#[allow(unused_imports)]use std::cmp::{max, min};#[allow(unused_imports)]use std::collections::btree_map::Entry::{Occupied, Vacant};#[allow(unused_imports)]use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};#[derive(PartialEq, PartialOrd, Debug, Clone)]struct Ordered<T: std::cmp::PartialOrd>(T);impl<T> Eq for Ordered<T>whereT: PartialOrd + Clone,{}impl<T> Ord for Ordered<T>whereT: PartialOrd + Clone,{fn cmp(&self, other: &Self) -> std::cmp::Ordering {self.partial_cmp(other).unwrap()}}impl<T: Copy + PartialOrd> Copy for Ordered<T> {}impl<T: std::cmp::PartialOrd> Ordered<T> {fn unwrap(self) -> T {let Ordered(res) = self;res}}#[derive(Eq, PartialEq, Clone, Debug)]struct Reverse<T>(T);impl<T: PartialOrd> PartialOrd for Reverse<T> {fn partial_cmp(&self, other: &Reverse<T>) -> Option<std::cmp::Ordering> {other.0.partial_cmp(&self.0)}}impl<T: Ord> Ord for Reverse<T> {fn cmp(&self, other: &Reverse<T>) -> std::cmp::Ordering {other.0.cmp(&self.0)}}fn main() {use std::io::Write;let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }let (n, k) = readl!(usize, usize);let a: Vec<i32> = readl!(String).into_bytes().into_iter().map(|x| if x == b'0' { 0 } else { 1 }).collect();if n == 1 {printfln!("{}", a[0]);return;}let check = |x: f64| {let mut a: Vec<_> = vec![0.].into_iter().chain(a.iter().cloned().chain(a.iter().cloned()).map(|e| e as f64 - x)).collect();debug!(a);for i in 0..a.len() - 1 {a[i + 1] += a[i];}debug!(a);let maxi: Vec<_> = sliding_minimum(&a.iter().cloned().map(|x| Reverse(Ordered(x))).collect(),n - k,).into_iter().map(|Reverse(Ordered(x))| x).collect();debug!(maxi);for (&l, &rmax) in a.iter().take(n+1).zip(maxi.iter().cycle().skip(k)) {if l < rmax {return false;}}true};debug!(check(1.));let mut l = 0.;let mut r = 1.;for _ in 0..20 {let m = (l + r) / 2.;let res = check(m);// debug!(res);if res {r = m;} else {l = m;}}printfln!("{}", r);}