結果
問題 |
No.3292 World Map Distance
|
ユーザー |
|
提出日時 | 2025-09-18 11:37:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 288 ms / 3,000 ms |
コード長 | 1,772 bytes |
コンパイル時間 | 12,490 ms |
コンパイル使用メモリ | 400,032 KB |
実行使用メモリ | 15,320 KB |
最終ジャッジ日時 | 2025-09-18 11:37:54 |
合計ジャッジ時間 | 20,380 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).unwrap(); ret } fn calc(xs: Vec<i64>, lim: i64) -> i64 { if lim == 1 { return 0; } let mut coo = xs.clone(); coo.push(0); coo.push(lim); for &x in &xs { coo.push((x + lim / 2) % lim); coo.push((x + lim - lim / 2) % lim); } coo.sort(); coo.dedup(); let m = coo.len(); let mut grad = vec![0; m]; let mut cur_grad = 0; let mut ma = 0; let mut cur = 0; for x in xs { let a = coo.binary_search(&x).unwrap(); let b = coo.binary_search(&((x + lim / 2) % lim)).unwrap(); let c = coo.binary_search(&((x + lim - lim / 2) % lim)).unwrap(); let mi = a.min(b).min(c); if mi == a { cur_grad -= 1; } else if mi == b { cur_grad += 1; } else { cur_grad += 0; } grad[a] += 2; grad[b] -= 1; grad[c] -= 1; cur += (lim - x).min(x); } for i in 0..m { ma = ma.max(cur); cur_grad += grad[i]; if i + 1 == m { break; } cur += cur_grad * (coo[i + 1] - coo[i]); } ma } fn main() { let ints = getline().trim() .split_whitespace() .map(|x| x.parse::<i64>().unwrap()) .collect::<Vec<_>>(); let [n, x, y] = ints[..] else { panic!() }; let mut xs = vec![]; let mut ys = vec![]; for _ in 0..n { let ints = getline().trim() .split_whitespace() .map(|x| x.parse::<i64>().unwrap()) .collect::<Vec<_>>(); let [a, b] = ints[..] else { panic!() }; xs.push(a - 1); ys.push(b - 1); } println!("{}", calc(xs, x) + calc(ys, y)); }