結果
問題 | No.2114 01 Matching |
ユーザー | akakimidori |
提出日時 | 2022-10-29 00:44:36 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,755 bytes |
コンパイル時間 | 11,576 ms |
コンパイル使用メモリ | 404,868 KB |
実行使用メモリ | 73,216 KB |
最終ジャッジ日時 | 2024-07-06 03:48:01 |
合計ジャッジ時間 | 23,576 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 227 ms
26,816 KB |
testcase_03 | AC | 52 ms
16,896 KB |
testcase_04 | AC | 74 ms
23,040 KB |
testcase_05 | WA | - |
testcase_06 | AC | 202 ms
24,964 KB |
testcase_07 | AC | 202 ms
20,256 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 196 ms
20,888 KB |
testcase_11 | AC | 368 ms
72,960 KB |
testcase_12 | AC | 368 ms
73,216 KB |
testcase_13 | WA | - |
testcase_14 | AC | 139 ms
37,504 KB |
testcase_15 | AC | 126 ms
37,504 KB |
testcase_16 | WA | - |
testcase_17 | AC | 204 ms
26,844 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 315 ms
73,088 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 329 ms
73,216 KB |
testcase_27 | AC | 332 ms
73,216 KB |
testcase_28 | AC | 164 ms
41,216 KB |
testcase_29 | AC | 320 ms
73,216 KB |
testcase_30 | AC | 194 ms
24,456 KB |
testcase_31 | AC | 343 ms
73,216 KB |
testcase_32 | WA | - |
testcase_33 | AC | 207 ms
28,904 KB |
testcase_34 | AC | 121 ms
21,660 KB |
testcase_35 | AC | 112 ms
30,848 KB |
testcase_36 | AC | 325 ms
73,216 KB |
testcase_37 | WA | - |
testcase_38 | AC | 196 ms
20,064 KB |
testcase_39 | WA | - |
testcase_40 | AC | 105 ms
30,336 KB |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 189 ms
25,324 KB |
testcase_44 | WA | - |
testcase_45 | AC | 201 ms
72,960 KB |
testcase_46 | WA | - |
testcase_47 | AC | 343 ms
72,832 KB |
testcase_48 | AC | 336 ms
73,088 KB |
testcase_49 | WA | - |
testcase_50 | WA | - |
testcase_51 | AC | 200 ms
27,916 KB |
testcase_52 | AC | 125 ms
37,632 KB |
ソースコード
// https://yukicoder.me/problems/no/1467// これっぽい感がfn run() {input! {n: usize,m: usize,k: i64,b: [i64; n],r: [i64; m],}let mut map = std::collections::BTreeMap::new();for &b in b.iter() {map.entry(b % k).or_insert(vec![vec![]; 2])[0].push(b / k);}for &r in r.iter() {map.entry(r % k).or_insert(vec![vec![]; 2])[1].push(r / k);}let mut sum = 0;let mut cnt = 0;let inf = std::i64::MAX / 10;for (_, mut p) in map {if p[0].len() > p[1].len() {p.swap(0, 1);}let mut a = vec![];a.extend(p[0].iter().map(|p| (*p, 0)));a.extend(p[1].iter().map(|p| (*p, 1)));a.sort();let mut left = std::collections::BinaryHeap::new();let mut left_add = 0;let mut right = std::collections::BinaryHeap::new();let mut right_add = 0;left.push((0, inf));right.push((0, inf));if a[0].1 == 0 {left_add += 1;right_add += 1;} else {left_add -= 1;}for a in a.windows(2) {let diff = a[1].0 - a[0].0;let mut d = diff;let mut l = 0;while d > 0 && left.peek().map_or(false, |p| p.0 + left_add > 0) {let (a, b) = *left.peek().unwrap();let a = a + left_add;let v = b.min(d);sum += a * v;d -= v;l += v;if b == v {left.pop();} else {left.peek_mut().unwrap().1 -= v;}right.push((-(a - right_add), v));}if d > 0 {right.push((right_add, d));}if l > 0 {left.push((left_add, d));}let mut d = diff;let mut r = 0;while d > 0 && right.peek().map_or(false, |p| -p.0 + right_add < 0) {let (a, b) = *right.peek().unwrap();let a = -a + right_add;let v = b.min(d);sum += -a * v;d -= v;r += v;if b == v {right.pop();} else {right.peek_mut().unwrap().1 -= v;}left.push((a - left_add, v));}if d > 0 {left.push((-left_add, d));}if r > 0 {right.push((right_add, r));}if a[1].1 == 0 {left_add += 1;right_add += 1;} else {left_add -= 1;}}for v in left.drain() {let pos = v.0 + left_add;let cnt = v.1;sum += cnt * std::cmp::max(pos, 0);}for v in right.drain() {let pos = -v.0 + right_add;let cnt = v.1;sum += cnt * std::cmp::max(-pos, 0);}cnt += p[0].len();}if cnt == n.min(m) {println!("{}", sum);} else {println!("-1");}}fn main() {run();}// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------