結果
問題 |
No.3128 Isosceles Triangle
|
ユーザー |
|
提出日時 | 2025-04-26 10:23:03 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 137 ms / 2,500 ms |
コード長 | 3,042 bytes |
コンパイル時間 | 13,769 ms |
コンパイル使用メモリ | 388,872 KB |
実行使用メモリ | 24,764 KB |
最終ジャッジ日時 | 2025-04-26 10:23:21 |
合計ジャッジ時間 | 16,988 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
fn main() { input!{ n: usize, mut a: [usize; n], } a.sort(); // 全て2倍しておく for i in 0..n { a[i] *= 2; } // 辺の種類毎の個数を数える let mut bmp = BTreeMap::new(); for &aa in &a { *bmp.entry(aa).or_insert(0) += 1usize; } // 累積和を作る(総和、XC2の総和) let mut arr = vec![0; 1]; let mut arr_acc = vec![0; 1]; let mut arr_xc2 = vec![0; 1]; for (&k, &v) in &bmp { let cur_xc2 = v * (v-1) / 2; let idx = arr.len()-1; // 前回idx arr.push(k); arr_acc.push(v + arr_acc[idx]); arr_xc2.push(cur_xc2 + arr_xc2[idx]); } // 短い辺2つと長い辺1つ // 長い方を全探索。(x-1以下の最大値 - x/2の以下の最大値) * 長い本数 // 長い辺2つと短い辺1つ // 長い方を全探索。(x-1以下の最大値) * 長い本数 / xC2 let mut ans = 0; for i in 1..arr.len() { let cnt = *bmp.get(&arr[i]).unwrap(); // x-1以下のmaxの位置 let pos1 = below_bound(&arr, arr[i]-1); // x/2以下のmaxの位置 let pos2 = below_bound(&arr, arr[i] / 2); // 短い辺2つと長い辺1つの個数 let mut cnt1 = 0; if pos1 != INFS { cnt1 = arr_xc2[pos1]; } let mut cnt2 = 0; if pos2 != INFS { cnt2 = arr_xc2[pos2]; } ans += cnt * (cnt1 - cnt2); // println!("add1: {}*{} ", cnt, cnt1 - cnt2); // 長い辺2つと短い辺1つ let xc2 = cnt * (cnt - 1) / 2; let mut cnt1 = 0; if pos1 != INFS { cnt1 = arr_acc[pos1]; } ans += xc2 * cnt1; // println!("add2: {} * {}", xc2 , cnt1); // println!(); } println!("{}", ans); } const INFS: usize = 1 << 60; // 二分探索 // x以下の最大のposを返す。0番目より小さい値では異常値として、「1<<60」を返す pub fn below_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize { let mut l = 0; let mut r = vec.len(); while r - l > 0 { let m = (l + r) / 2; if vec[m] <= val { l = m + 1; } else { r = m; } } if l == 0 { INFS } else {l-1} } // 二分探索 // x以上の最小のposを返す pub fn lower_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize { let mut l = 0; let mut r = vec.len(); while r - l > 0 { let m = (l + r) / 2; if vec[m] < val { l = m + 1; } else { r = m; } } l } // const MOD17: usize = 1000000007; // const MOD93: usize = 998244353; // const INF: usize = 1 << 60; // let dx = vec![!0, 0, 1, 0]; // 上左下右 // let dy = vec![0, !0, 0, 1]; // 上左下右 // let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右 #[allow(unused)] use proconio::{input, marker::Chars, marker::Usize1}; #[allow(unused)] use std::{ mem::swap, cmp::min, cmp::max, cmp::Reverse, collections::HashSet, collections::BTreeSet, collections::HashMap, collections::BTreeMap, collections::BinaryHeap, collections::VecDeque, iter::FromIterator, }; // 配列のスペース区切り出力 #[allow(unused)] fn vec_print<T: std::fmt::Display>(vec: &Vec<T>) { let sz = vec.len(); for i in 0..sz-1 { print!("{} ", vec[i]); } println!("{}", vec[sz-1]); }