https://atcoder.jp/contests/abc271/tasks/abc271_c
BTreeSetを使って、一つずつtreeにinsertして、重複分は十分大きな値にしてinsertします。
最初はVecを使って実装しましたが、そちらの方が速かったようです。
// Manga #![allow(non_snake_case)] use std::cmp::max; use std::collections::BTreeSet; 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() } fn read_input() -> Vec<usize> { let _N: usize = read(); let A = read_vec(); A } fn make_tree(A: Vec<usize>) -> BTreeSet<usize> { let mut current = max(A.len(), *A.iter().max().unwrap()) + 1; let mut tree = BTreeSet::<usize>::new(); for &a in A.iter() { if tree.contains(&a) { tree.insert(current); current += 1 } else { tree.insert(a); } } tree } fn f(A: Vec<usize>) -> usize { let mut tree = make_tree(A); for n in 1usize.. { if tree.contains(&n) { tree.remove(&n); } else { match tree.iter().last() { Some(&m) => tree.remove(&m), None => return n - 1 }; match tree.iter().last() { Some(&m) => tree.remove(&m), None => return n - 1 }; } } return 0 // dummy } fn main() { let A = read_input(); println!("{}", f(A)) }