結果
問題 | No.794 チーム戦 (2) |
ユーザー |
|
提出日時 | 2023-01-19 00:08:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 40 ms / 1,500 ms |
コード長 | 1,871 bytes |
コンパイル時間 | 12,529 ms |
コンパイル使用メモリ | 402,464 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-06-11 23:39:19 |
合計ジャッジ時間 | 15,568 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
warning: function `lower_bound` is never used --> src/main.rs:4:4 | 4 | fn lower_bound(target: usize, vals: &Vec<usize>) -> usize { | ^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
const MOD: usize = 1e9 as usize + 7;fn lower_bound(target: usize, vals: &Vec<usize>) -> usize {let mut upper = vals.len();let mut lower = 0usize;while upper > lower {let middle = (upper + lower) / 2;if vals[middle] < target {lower = middle+1;} else {upper = middle;}}upper}fn upper_bound(target: usize, vals: &Vec<usize>) -> usize {let mut upper = vals.len();let mut lower = 0usize;while upper > lower {let middle = (upper + lower) / 2;if vals[middle] <= target {lower = middle+1;} else {upper = middle;}}upper}fn main() {let mut nk = String::new();std::io::stdin().read_line(&mut nk).ok();let nk: Vec<usize> = nk.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();let n = nk[0];let k = nk[1];let mut a = String::new();std::io::stdin().read_line(&mut a).ok();let a: Vec<usize> = a.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();if a.iter().any(|&v| v > k) {println!("0");return;}let mut uppers = a.iter().filter(|&&v| v > k/2).copied().collect::<Vec<_>>();let mut lowers = a.iter().filter(|&&v| v <= k/2).copied().collect::<Vec<_>>();if uppers.len() > n/2 {println!("0");return;}uppers.sort();uppers.reverse();lowers.sort();let mut result = 1usize;for i in 0..uppers.len() {let left = upper_bound(k-uppers[i], &lowers);if left <= i {println!("0");return;}result *= left - i;result %= MOD;}let limit = lowers.len() - uppers.len();for i in 0..limit/2 {result *= limit-2*i-1;result %= MOD;}println!("{}", result);}