AtCoder Beginner Contest 424 E

https://atcoder.jp/contests/abc424/tasks/abc424_e

Priority Queueを使って長い棒から順に切断していくだけですが、元の棒が同じものはまとめて切らないと間に合わないけれど、端数が出るときは調整して、Priority Queueにそのまま戻さないといけません。

// Cut in Half
#![allow(non_snake_case)]


//////////////////// library ////////////////////

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

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


//////////////////// Test ////////////////////

struct Test {
    K: usize,
    X: usize,
    A: Vec<i32>
}

impl Test {
    fn read() -> Test {
        let v: Vec<usize> = read_vec();
        let (K, X) = (v[1], v[2]);
        let A: Vec<i32> = read_vec();
        Test { K, X, A }
    }
}


//////////////////// Item ////////////////////

use std::cmp::Ordering;

#[derive(Debug, Copy, Clone, PartialEq)]
struct Item {
    length: f64,
    num: usize
}

impl Item {
    fn new(length: f64, num: usize) -> Item {
        Item { length, num }
    }
}

impl Eq for Item {}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other).unwrap_or(Ordering::Less)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.length.partial_cmp(&other.length)
    }
}


//////////////////// process ////////////////////

use std::collections::BinaryHeap;

fn F_each(test: Test) -> f64 {
    let mut c: usize = 0;
    let mut pq: BinaryHeap<Item> = BinaryHeap::new();
    for &a in test.A.iter() {
        pq.push(Item::new(a as f64, 1))
    }
    
    while let Some(item) = pq.pop() {
        if c + item.num < test.K {
            c += item.num;
            pq.push(Item::new(item.length*0.5, item.num*2))
        }
        else {
            pq.push(Item::new(item.length, c+item.num-test.K));
            pq.push(Item::new(item.length*0.5, (test.K-c)*2));
            break
        }
    }
    
    let mut x: usize = 0;
    while let Some(item2) = pq.pop() {
        x += item2.num;
        if x >= test.X {
            return item2.length
        }
    }
    0.0
}

fn F(T: usize) {
    for _ in 0..T {
        let test = Test::read();
        println!("{}", F_each(test))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}