結果

問題 No.1730 GCD on Blackboard in yukicoder
ユーザー katandkatand
提出日時 2021-11-05 21:54:33
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,046 ms / 2,000 ms
コード長 5,616 bytes
コンパイル時間 980 ms
コンパイル使用メモリ 180,560 KB
実行使用メモリ 23,652 KB
最終ジャッジ日時 2024-04-25 17:21:09
合計ジャッジ時間 10,635 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,046 ms
16,612 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 8 ms
9,736 KB
testcase_03 AC 6 ms
9,676 KB
testcase_04 AC 6 ms
9,736 KB
testcase_05 AC 7 ms
9,616 KB
testcase_06 AC 6 ms
9,620 KB
testcase_07 AC 6 ms
9,640 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 6 ms
7,856 KB
testcase_10 AC 5 ms
8,080 KB
testcase_11 AC 2 ms
6,948 KB
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 599 ms
22,120 KB
testcase_14 AC 598 ms
22,372 KB
testcase_15 AC 598 ms
22,128 KB
testcase_16 AC 602 ms
23,652 KB
testcase_17 AC 597 ms
22,240 KB
testcase_18 AC 297 ms
17,740 KB
testcase_19 AC 799 ms
22,008 KB
testcase_20 AC 151 ms
20,688 KB
testcase_21 AC 151 ms
20,984 KB
testcase_22 AC 848 ms
18,784 KB
testcase_23 AC 43 ms
14,524 KB
testcase_24 AC 49 ms
20,620 KB
testcase_25 AC 525 ms
19,420 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/// general import
pub use std::{
    cmp::{max, min, Ordering, Reverse},
    collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque},
    convert::Infallible,
    convert::{TryFrom, TryInto},
    fmt::{Debug, Display, Formatter},
    io::{stdin, stdout, BufRead, BufWriter, Write},
    iter::{Product, Sum},
    marker::PhantomData,
    mem::swap,
    ops::{
        Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Bound,
        Deref, DerefMut, Div, DivAssign, Mul, MulAssign, Neg, Not, RangeBounds, Rem, RemAssign,
        Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
    },
    str::{from_utf8, FromStr},
};

/// min-max macros
#[allow(unused_macros)]
macro_rules! chmin {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_min = min!($($cmps),+);if $base > cmp_min {$base = cmp_min;true} else {false}}};}
#[allow(unused_macros)]
macro_rules! chmax {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_max = max!($($cmps),+);if $base < cmp_max {$base = cmp_max;true} else {false}}};}
#[allow(unused_macros)]
macro_rules! min {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{if $a > $b {$b} else {$a}}};($a:expr, $($rest:expr),+ $(,)*) => {{let b = min!($($rest),+);if $a > b {b} else {$a}}};}
#[allow(unused_macros)]
macro_rules! max {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{if $a > $b {$a} else {$b}}};($a:expr, $($rest:expr),+ $(,)*) => {{let b = max!($($rest),+);if $a > b {$a} else {b}}};}

pub fn to_lr<R: RangeBounds<usize>>(range: &R, length: usize) -> (usize, usize) {
    let l = match range.start_bound() {
        Bound::Unbounded => 0,
        Bound::Included(&s) => s,
        Bound::Excluded(&s) => s + 1,
    };
    let r = match range.end_bound() {
        Bound::Unbounded => length,
        Bound::Included(&e) => e + 1,
        Bound::Excluded(&e) => e,
    };
    assert!(l <= r && r <= length);
    (l, r)
}

/// stdin reader
pub struct Reader<R> {
    reader: R,
    buf: VecDeque<String>,
}
impl<R: BufRead> Iterator for Reader<R> {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        if self.buf.is_empty() {
            let mut buf = Vec::new();
            self.reader.read_to_end(&mut buf).unwrap();
            let s = from_utf8(&buf).expect("utf8でない文字列が入力されました.");
            s.split_whitespace()
                .map(ToString::to_string)
                .for_each(|s| self.buf.push_back(s));
        }
        self.buf.pop_front()
    }
}
impl<R: BufRead> Reader<R> {
    pub fn new(reader: R) -> Reader<R> {
        Reader {
            reader,
            buf: VecDeque::new(),
        }
    }
    pub fn val<T: FromStr>(&mut self) -> T {
        self.next()
            .map(|token| token.parse().ok().expect("型変換エラー"))
            .expect("入力が足りません")
    }
    pub fn vec<T: FromStr>(&mut self, length: usize) -> Vec<T> {
        (0..length).map(|_| self.val()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.val::<String>().chars().collect()
    }
    pub fn digits(&mut self) -> Vec<i64> {
        self.val::<String>()
            .chars()
            .map(|c| (c as u8 - b'0') as i64)
            .collect()
    }
    pub fn char_map(&mut self, h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| self.chars()).collect()
    }
    pub fn bool_map(&mut self, h: usize, ng: char) -> Vec<Vec<bool>> {
        self.char_map(h)
            .iter()
            .map(|v| v.iter().map(|&c| c != ng).collect())
            .collect()
    }
    pub fn matrix<T: FromStr>(&mut self, h: usize, w: usize) -> Vec<Vec<T>> {
        (0..h).map(|_| self.vec(w)).collect()
    }
}

/// stdin writer
pub struct Writer<W: Write> {
    writer: BufWriter<W>,
}
impl<W: Write> Writer<W> {
    pub fn new(write: W) -> Self {
        Self {
            writer: BufWriter::new(write),
        }
    }
    pub fn println<S: Display>(&mut self, s: S) {
        writeln!(self.writer, "{}", s).expect("Failed to write.")
    }
    pub fn print<S: Display>(&mut self, s: S) {
        write!(self.writer, "{}", s).expect("Failed to write.")
    }
    pub fn print_join<S: Display>(&mut self, v: &[S], separator: &str) {
        v.iter().fold("", |sep, arg| {
            write!(self.writer, "{}{}", sep, arg).expect("Failed to write.");
            separator
        });
        writeln!(self.writer).expect("Failed to write.");
    }
}

#[allow(dead_code)]
fn main() {
    let stdin = stdin();
    let stdout = stdout();
    solve(Reader::new(stdin.lock()), Writer::new(stdout.lock()));
}

pub fn solve<R: BufRead, W: Write>(mut reader: Reader<R>, mut writer: Writer<W>) {
    let n = reader.val::<usize>();
    let a = reader.vec::<i64>(n);

    const MAX: usize = 1000010;
    let mut counts = vec![0; MAX];
    for ai in a {
        let mut l = 1;
        while l * l <= ai {
            if ai % l == 0 {
                counts[l as usize] += 1;
                if ai / l != l {
                    counts[(ai / l) as usize] += 1;
                }
            }
            l += 1;
        }
    }

    for i in (1..MAX).rev() {
        chmax!(counts[i - 1], counts[i]);
    }

    let mut ans = vec![0; n + 1];
    for i in 1..=n {
        ans[n - i] = binary_search(-1, MAX as i64 + 1, |mid| counts[mid as usize] >= i);
    }
    writer.print_join(&ans[0..n], "\n");
}

pub fn binary_search<F: Fn(i64) -> bool>(mut ok: i64, mut ng: i64, f: F) -> i64 {
    while (ok - ng).abs() > 1 {
        let mid = (ok + ng) / 2;
        if f(mid) {
            ok = mid
        } else {
            ng = mid
        }
    }
    ok
}
0