提出 #19235690

---

ソースコード 拡げる

use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;

const MOD: i64 = 1e9 as i64 + 7;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let a: i64 = sc.read();
    let mut b: usize = sc.read();
    let mut arr: Vec<i64> = sc.vec(n);

    if a == 1 {
        arr.sort();
        for i in 0..n {
            println!("{}", arr[i]);
        }
        return;
    }

    let mut heap = BinaryHeap::new();
    let mut cur_max = 0.0f64;

    for i in 0..n {
        let a = (arr[i] as f64).log2();
        heap.push((Reverse(F64(a)), 0, i));
        cur_max = cur_max.max(a);
    }

    while b > 0 && heap.peek().cloned().unwrap().0 .0 .0 + (a as f64).log2() < cur_max {
        let mut minimum = heap.pop().unwrap();
        minimum.0 .0 .0 += (a as f64).log2();
        minimum.1 += 1;
        cur_max = cur_max.max(minimum.0 .0 .0);
        heap.push(minimum);
        b -= 1;
    }

    let one_b = b / n;
    for _ in 0..n {
        let mut minimum = heap.pop().unwrap();
        minimum.0 .0 .0 += (a as f64).log2() * one_b as f64;
        minimum.1 += one_b;
        heap.push(minimum);
    }
    for _ in 0..(b % n) {
        let mut minimum = heap.pop().unwrap();
        minimum.0 .0 .0 += (a as f64).log2();
        minimum.1 += 1;
        heap.push(minimum);
    }

    while let Some((_, count, i)) = heap.pop() {
        let pow = mod_pow(a, count);
        println!("{}", (pow * arr[i]) % MOD);
    }
}

fn mod_pow(mut x: i64, mut e: usize) -> i64 {
    let mut result = 1;
    while e > 0 {
        if e & 1 == 1 {
            result = (result * x) % MOD;
        }
        x = (x * x) % MOD;
        e >>= 1;
    }
    result
}

#[derive(PartialEq, Copy, Clone)]
struct F64(f64);

impl Eq for F64 {}
impl PartialOrd for F64 {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.0.partial_cmp(&other.0)
    }
}

impl Ord for F64 {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(&other).unwrap()
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

提出情報

ジャッジ結果