結果

問題 No.794 チーム戦 (2)
ユーザー phsplsphspls
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0