結果

問題 No.2453 Seat Allocation
ユーザー ikomaikoma
提出日時 2023-09-01 23:41:07
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,640 bytes
コンパイル時間 16,379 ms
コンパイル使用メモリ 378,464 KB
実行使用メモリ 17,540 KB
最終ジャッジ日時 2025-01-03 12:54:45
合計ジャッジ時間 35,626 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 16 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    let mut input_iter = input.split_whitespace();
    
    let _: usize = input_iter.next().unwrap().parse().unwrap();
    let _: usize = input_iter.next().unwrap().parse().unwrap();
    
    input.clear();
    std::io::stdin().read_line(&mut input).unwrap();
    let a: Vec<i64> = input.split_whitespace().map(|x| x.parse().unwrap()).collect();
    
    input.clear();
    std::io::stdin().read_line(&mut input).unwrap();
    let b: Vec<i64> = input.split_whitespace().map(|x| x.parse().unwrap()).collect();
    
    let mut ai: Vec<(i64, usize)> = a.iter().enumerate().map(|(i, &x)| (x, i)).collect();
    ai.sort_by_key(|x| Reverse(x.0));
    
    let mut heap: BinaryHeap<(i64, usize)> = BinaryHeap::new(); // u64型を使用
    
    let (a_max, i_max) = ai[0];
    for &b_j in b.iter() {
        let p = (a_max as f64 / b_j as f64 * 1e6) as i64; 
        heap.push((-p, i_max));
    }
    
    for &(a_i, i) in ai.iter().skip(1) {
        for &b_j in b.iter() {
            let p = (a_i as f64 / b_j as f64 * 1e6) as i64; // 小数点以下を考慮
            heap.push((-p, i)); // u64型を使用
            if let Some((p2, i2)) = heap.pop() {
                if p != -p2 || i != i2 {
                    break;
                }
            }
        }
    }
    
    let mut ans: Vec<usize> = Vec::new();
    while let Some((_, i)) = heap.pop() {
        ans.push(i+1);
    }
    
    ans.reverse();
    
    for &x in ans.iter() {
        println!("{}", x);
    }
}
0