Submission #8630603


Source Code Expand

Copy
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let s = read::<String>().chars().collect::<Vec<_>>();
    let mut zero_poses = vec![];
    for i in 0..n + 1 {
        if s[i] == '0' {
            zero_poses.push(i);
        }
    }
    let mut from = vec![std::usize::MAX; n + 1];
    for i in 1..n + 1 {
        let mut search_min = max(0, i as i64 - m as i64) as usize;
        let idx = zero_poses[zero_poses.lower_bound(&search_min)];
        if idx == zero_poses.len() {
            continue;
        }
        from[i] = idx;
    }
    if from[n] == std::usize::MAX {
        println!("-1");
        return;
    }
    let mut pointer = n;
    let mut answers = vec![];
    while pointer != 0 {
        let next = from[pointer];
        answers.push(pointer - next);
        if pointer == next {
            println!("-1");
            return;
        }
        pointer = next;
    }
    answers.reverse();
    print_array(&answers);
}

pub trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}

fn print_array<T: std::string::ToString>(array: &Vec<T>) {
    println!(
        "{}",
        array
            .iter()
            .map(|ref x| x.to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

Submission Info

Submission Time
Task F - Sugoroku
User ryoryoryo111
Language Rust (1.15.1)
Score 600
Code Size 2943 Byte
Status AC
Exec Time 21 ms
Memory 12668 KB

Compile Error

warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
  --> ./Main.rs:30:13
   |
30 |         let mut search_min = max(0, i as i64 - m as i64) as usize;
   |             ^^^^^^^^^^^^^^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 60
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49, 02-random-50, 02-random-51, 02-random-52, 02-random-53, 02-random-54, 02-random-55, 02-random-56, 02-random-57, 02-random-58, 02-random-59
Case Name Status Exec Time Memory
00-sample-00 AC 2 ms 4352 KB
00-sample-01 AC 2 ms 4352 KB
00-sample-02 AC 2 ms 4352 KB
01-handmade-03 AC 2 ms 4352 KB
01-handmade-04 AC 9 ms 6396 KB
01-handmade-05 AC 10 ms 6396 KB
01-handmade-06 AC 8 ms 6396 KB
01-handmade-07 AC 3 ms 4352 KB
01-handmade-08 AC 8 ms 6396 KB
01-handmade-09 AC 21 ms 12668 KB
01-handmade-10 AC 9 ms 6396 KB
02-random-11 AC 8 ms 6396 KB
02-random-12 AC 9 ms 6396 KB
02-random-13 AC 8 ms 6396 KB
02-random-14 AC 8 ms 6396 KB
02-random-15 AC 8 ms 6396 KB
02-random-16 AC 10 ms 6396 KB
02-random-17 AC 8 ms 6396 KB
02-random-18 AC 8 ms 6396 KB
02-random-19 AC 8 ms 6396 KB
02-random-20 AC 8 ms 6396 KB
02-random-21 AC 9 ms 6396 KB
02-random-22 AC 9 ms 6396 KB
02-random-23 AC 8 ms 6396 KB
02-random-24 AC 8 ms 6396 KB
02-random-25 AC 8 ms 6396 KB
02-random-26 AC 8 ms 6396 KB
02-random-27 AC 7 ms 6396 KB
02-random-28 AC 7 ms 6396 KB
02-random-29 AC 8 ms 6396 KB
02-random-30 AC 8 ms 6396 KB
02-random-31 AC 8 ms 6396 KB
02-random-32 AC 8 ms 6396 KB
02-random-33 AC 8 ms 6396 KB
02-random-34 AC 8 ms 6396 KB
02-random-35 AC 8 ms 6396 KB
02-random-36 AC 8 ms 6396 KB
02-random-37 AC 7 ms 6396 KB
02-random-38 AC 7 ms 6396 KB
02-random-39 AC 8 ms 6396 KB
02-random-40 AC 8 ms 6396 KB
02-random-41 AC 7 ms 6396 KB
02-random-42 AC 7 ms 6396 KB
02-random-43 AC 8 ms 6396 KB
02-random-44 AC 7 ms 4352 KB
02-random-45 AC 7 ms 4352 KB
02-random-46 AC 8 ms 6396 KB
02-random-47 AC 7 ms 4352 KB
02-random-48 AC 6 ms 4352 KB
02-random-49 AC 7 ms 4352 KB
02-random-50 AC 6 ms 4352 KB
02-random-51 AC 7 ms 4352 KB
02-random-52 AC 7 ms 4352 KB
02-random-53 AC 6 ms 4352 KB
02-random-54 AC 7 ms 4352 KB
02-random-55 AC 6 ms 4352 KB
02-random-56 AC 6 ms 4352 KB
02-random-57 AC 6 ms 4352 KB
02-random-58 AC 5 ms 4352 KB
02-random-59 AC 5 ms 4352 KB