結果
問題 | No.2918 Divide Applicants Fairly |
ユーザー |
|
提出日時 | 2024-10-08 13:38:04 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,036 ms / 2,000 ms |
コード長 | 4,379 bytes |
コンパイル時間 | 12,960 ms |
コンパイル使用メモリ | 404,240 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-12-14 00:33:36 |
合計ジャッジ時間 | 19,078 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#[allow(unused_imports)]use std::{collections::{HashSet, HashMap, BinaryHeap, VecDeque, BTreeSet, BTreeMap},mem::{swap},cmp::{Reverse, Ordering, PartialOrd, PartialEq},fmt::{Debug},time::Instant};//#[allow(unused_imports)]//use rand::{Rng, thread_rng, seq::{SliceRandom, IndexedRandom}};use std::io::{Read, BufReader, stdin};struct InputReader<R: Read> {bytes: std::iter::Peekable<std::io::Bytes<BufReader<R>>>,}impl<R: Read> InputReader<R> {fn new(reader: R) -> Self {let reader = BufReader::new(reader);let bytes = reader.bytes().peekable();Self { bytes }}fn next_token(&mut self) -> String {self.bytes.by_ref().map(|r| r.unwrap() as char).take_while(|c| !c.is_whitespace()).collect()}}macro_rules! input {($reader:expr, $($r:tt)*) => {let mut next = || $reader.next_token();input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, usize) => {$next().parse::<usize>().expect("Parse error")};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}fn main() {let stdin = stdin();let mut reader = InputReader::new(stdin.lock());input!{reader,n: usize,r: [i64; n],}if n > 25{println!("0");return;}let h1 = &r[..n/2];let h2 = &r[n/2..];let mut ans = 1<<60;let mut set1 = HashMap::new();let mut set2 = HashMap::new();let mut set3 = HashMap::new();for i in 0..3i64.pow(h1.len() as u32){let mut cnt = 0;let mut z = 0;let mut x = i;let (mut f1, mut f2) = (false, false);for j in 0..h1.len(){if x%3==0{f1 = true;z += h1[j];cnt += 1;} else if x%3==1{f2 = true;z -= h1[j];cnt -= 1;}x /= 3;}if f1 && f2{set1.entry(cnt).or_insert(BTreeSet::new()).insert(z);} else if f1{set2.entry(cnt).or_insert(BTreeSet::new()).insert(z);} else if f2{set3.entry(cnt).or_insert(BTreeSet::new()).insert(z);}}for i in 0..3i64.pow(h2.len() as u32){let mut z = 0;let mut x = i;let mut cnt = 0;let (mut f1, mut f2) = (false, false);for j in 0..h2.len(){if x%3==0{f1 = true;z += h2[j];cnt -= 1;} else if x%3==1{f2 = true;z -= h2[j];cnt += 1;}x /= 3;}if let Some(v) = set1.get(&cnt){if let Some(&p) = v.range(-z..).next(){ans = ans.min((p+z).abs());}if let Some(&p) = v.range(..-z).next_back(){ans = ans.min((p+z).abs());}}if f1{if let Some(v) = set3.get(&cnt){if let Some(&p) = v.range(-z..).next(){ans = ans.min((p+z).abs());}if let Some(&p) = v.range(..-z).next_back(){ans = ans.min((p+z).abs());}}}if f2{if let Some(v) = set2.get(&cnt){if let Some(&p) = v.range(-z..).next(){ans = ans.min((p+z).abs());}if let Some(&p) = v.range(..-z).next_back(){ans = ans.min((p+z).abs());}}}}println!("{}", ans);}