結果

問題 No.5019 Hakai Project
ユーザー tttttaaa
提出日時 2023-11-24 18:48:13
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 361 ms / 3,000 ms
コード長 13,690 bytes
コンパイル時間 3,234 ms
コンパイル使用メモリ 208,296 KB
実行使用メモリ 184,832 KB
スコア 1,825,434,443
最終ジャッジ日時 2023-11-24 18:48:39
合計ジャッジ時間 24,051 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `FN`
   --> Main.rs:213:9
    |
213 |     let FN = 10;
    |         ^^ help: if this is intentional, prefix it with an underscore: `_FN`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `writer`
   --> Main.rs:247:13
    |
247 |     let mut writer = std::io::BufWriter::new(stdout.lock());
    |             ^^^^^^ help: if this is intentional, prefix it with an underscore: `_writer`

warning: variable does not need to be mutable
   --> Main.rs:247:9
    |
247 |     let mut writer = std::io::BufWriter::new(stdout.lock());
    |         ----^^^^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: 3 warnings emitted

ソースコード

diff #
プレゼンテーションモードにする

#![allow(unused_imports, non_snake_case, dead_code)]
pub use __cargo_equip::prelude::*;
use kyopro_grid::{D4, P};
use kyopro_io::get;
use kyopro_utils::*;
use std::collections::BTreeSet;
use std::mem::{self, swap};
use std::ops::{Index, IndexMut};
use std::{
cmp::max,
collections::BTreeMap,
io::{StdoutLock, Write},
};
const N: usize = 50;
const M: usize = 20;
struct Bomb {
C: usize,
L: usize,
ab: Vec<(i32, i32)>,
}
struct Input {
A: Vec<Vec<char>>,
bs: Vec<Bomb>,
shops: Vec<P>,
}
fn read_input() -> Input {
let _ = get!(usize, usize);
let A = (0..N).map(|_| get!(String).chars().collect::<Vec<_>>()).collect::<Vec<_>>();
let mut bs = vec![];
for _ in 0..M {
let (c, l) = get!(usize, usize);
let mut ab = vec![];
for _ in 0..l {
let (a, b) = get!(i32, i32);
ab.push((a, b));
}
bs.push(Bomb { C: c, L: l, ab });
}
let mut shops = vec![];
for i in 0..N {
for j in 0..N {
if A[i][j] == '@' {
shops.push(P(i, j));
}
}
}
Input { A, bs, shops }
}
fn get_bpoints(p: P, ab: &[(i32, i32)], inv: bool) -> Vec<P> {
let mut res = vec![];
for &(a, b) in ab {
let ni = p.0 as i32 + (if inv { -a } else { a });
let nj = p.1 as i32 + (if inv { -b } else { b });
if 0 <= ni && ni < N as i32 && 0 <= nj && nj < N as i32 {
let ni = ni as usize;
let nj = nj as usize;
res.push(P(ni, nj));
}
}
res
}
fn greedy2(
inp: &Input,
shops: &[P],
p_to_bp: &Vec<Vec<Vec<Vec<P>>>>,
pb_cnt: &Vec<Vec<Vec<i32>>>,
) -> Vec<(usize, usize)> {
let mut dcost = mat![0;N;N];
let mut shop_to_npts = mat![vec![];shops.len()];
for i in 0..N {
for j in 0..N {
let p = P(i, j);
let mut near_shop = 0;
let mut d = !0;
for (si, sp) in shops.iter().enumerate() {
if d.setmin(sp.dist(&p)) {
near_shop = si;
}
}
dcost[p] = d;
shop_to_npts[near_shop].push(p);
}
}
let kill = |g: &mut Vec<Vec<char>>, pb_cnt: &mut Vec<Vec<Vec<i32>>>, p: P| {
if g[p] == '.' {
return;
}
g[p] = '.';
for i in 0..M {
for &np in &p_to_bp[p][i] {
pb_cnt[np][i] -= 1;
}
}
};
let mut ng_pbs = mat![0;N;N;M];
for (i, &p) in shops.iter().enumerate() {
for m in 0..M {
for np in get_bpoints(p, &inp.bs[m].ab, true) {
ng_pbs[np][m] |= 1usize << (i + 1);
}
}
}
let mut g = inp.A.clone();
let mut pb_cnt = pb_cnt.clone();
let mut use_bi_at_shops = vec![0; shops.len()];
for (si, &sp) in shops.iter().enumerate() {
let mut x = 0.0;
let mut bi = 0;
for m in 0..M {
if ng_pbs[sp][m] >> si > 0 {
continue;
}
let mut tot = 0;
for bp in get_bpoints(sp, &inp.bs[m].ab, false) {
tot += pb_cnt[bp][m];
}
if x.setmax(tot as f64 / inp.bs[m].C as f64) {
bi = m;
}
}
use_bi_at_shops[si] = bi;
{
for bp in get_bpoints(sp, &inp.bs[bi].ab, false) {
kill(&mut g, &mut pb_cnt, bp);
}
}
}
let mut curr_shop_i = 0;
// TODO:move to shop[0]
let mut res = move_to(&g, P(0, 0), shops[0]);
let mut iter = 0;
while curr_shop_i < shops.len() {
iter += 1;
let can_fire = |p: P, m: usize| ng_pbs[p][m] >> (curr_shop_i + 1) == 0;
let mut ri = 0.0;
let mut best_pm = (P(0, 0), !0);
for &bp in &shop_to_npts[curr_shop_i] {
for m in 0..M {
if can_fire(bp, m) {
if pb_cnt[bp][m] <= 0 {
continue;
}
let val = pb_cnt[bp][m] as f64;
let co = inp.bs[m].C as f64 + (dcost[bp]*dcost[bp]) as f64;
if ri.setmax(val / co) {
best_pm = (bp, m);
}
}
}
}
if best_pm.1 == !0 {
// TODO:shop bomb
let m = use_bi_at_shops[curr_shop_i];
res.push((2, m + 1));
res.push((3, m + 1));
curr_shop_i += 1;
} else {
if iter > 100 {
break;
}
// TODO:m bp m bomb
let (p, m) = best_pm;
res.push((2, m + 1));
// TODO:shop[curr_shop_i]
let mut tmp = move_to(&g, shops[curr_shop_i], p);
res.append(&mut tmp);
res.push((3, m + 1));
for bp in get_bpoints(p, &inp.bs[m].ab, false) {
assert!(bp != shops[curr_shop_i]);
kill(&mut g, &mut pb_cnt, bp);
}
let mut tmp = move_to(&g, p, shops[curr_shop_i]);
res.append(&mut tmp);
}
}
res
}
const DC: [char; 4] = ['D', 'R', 'U', 'L'];
fn move_to(_g: &Vec<Vec<char>>, f: P, t: P) -> Vec<(usize, usize)> {
let mut now = f;
let mut res = vec![];
while now.0 < t.0 {
res.push((1, 0));
now.0 += 1;
}
while now.0 > t.0 {
res.push((1, 2));
now.0 -= 1;
}
while now.1 < t.1 {
res.push((1, 1));
now.1 += 1;
}
while now.1 > t.1 {
res.push((1, 3));
now.1 -= 1;
}
res
}
fn greedy(inp: &Input) {
let FN = 10;
let fshop = inp.shops.iter().enumerate().min_by_key(|(_, &p)| p.0 + p.1).unwrap().0;
let mut use_shops = vec![false; inp.shops.len()];
use_shops[fshop] = true;
let use_shops =
(0..inp.shops.len()).filter_map(|i| if use_shops[i] { Some(inp.shops[i]) } else { None }).collect::<Vec<_>>();
let mut p_to_bp = mat![vec![];N;N;M]; // [i][j][b]: bomb b P(i,j)
let mut pb_cnt = mat![0i32;N;N;M]; // [i][j][b]: P(i,j) b 使
for i in 0..N {
for j in 0..N {
if inp.A[i][j] == '.' {
continue;
}
for k in 0..M {
for np in get_bpoints(P(i, j), &inp.bs[k].ab, true) {
p_to_bp[i][j][k].push(np);
pb_cnt[np][k] += 1;
}
}
}
}
let res = greedy2(inp, &use_shops, &p_to_bp, &pb_cnt);
println!("{}", res.len());
for &(a, b) in &res {
if a == 1 {
println!("1 {}", DC[b]);
} else {
println!("{} {}", a, b);
}
}
}
fn main() {
let stdout = std::io::stdout();
let mut writer = std::io::BufWriter::new(stdout.lock());
let inp = read_input();
greedy(&inp);
// writeln!(writer, "1").unwrap();
// writeln!(writer, "1 D").unwrap();
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `kyopro-grid 0.1.0 (path+██████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::kyopro_grid`
/// - `kyopro-io 0.1.0 (path+████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::kyopro_io`
/// - `kyopro-utils 0.1.0 (path+███████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::kyopro_utils`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod kyopro_grid {use std::ops::{Index,IndexMut};pub const D4:[P;4]=[P(1,0),P(0,1),P(!0,0),P(0,!0)];#[derive(Clone,Copy,PartialEq,Eq,Debug
            )]pub struct P(pub usize,pub usize);impl P{pub fn adj4(self)->impl Iterator<Item=P>{D4.iter().map(move|&d|self.add(&P(d.0,d.1)))}pub fn
            add(self,rhs:&P)->P{P(self.0.wrapping_add(rhs.0),self.1.wrapping_add(rhs.1))}pub fn dist(&self,rhp:&P)->usize{let a=(self.0 as i32-rhp.0
            as i32)as usize;let b=(self.1 as i32-rhp.1 as i32)as usize;a+b}}impl<T>Index<P>for Vec<Vec<T>>{type Output=T;fn index(&self,p:P
            )->&T{&self[p.0][p.1]}}impl<T>IndexMut<P>for Vec<Vec<T>>{fn index_mut(&mut self,p:P)->&mut T{&mut self[p.0][p.1]}}pub struct Grid<T>{h
            :usize,w:usize,g:Vec<Vec<T>>,}impl<T>Grid<T>where T:Copy,{pub fn from(g:&Vec<Vec<T>>)->Self{Grid{h:g.len(),w:g[0].len(),g:g.clone
            ()}}#[allow(non_snake_case)]pub fn new(h:usize,w:usize,I:T)->Self{let g=vec![vec![I;w];h];Grid{h,w,g}}}impl<T>Grid<T>{pub fn adj4<'a>(&'a
            self,p:P)->impl Iterator<Item=P>+'a{D4.iter().map(move|&d|p.add(&P(d.0,d.1))).filter(|&p|p.0<self.h&&p.1<self.w)}pub fn positions_from<'a
            >(&'a self,b:P,offsets:&'a[P])->impl Iterator<Item=P>+'a{let x=offsets.iter().map(move|&d|P(b.0.wrapping_add(d.0),b.1.wrapping_add(d.1
            )));x.filter(|&p|p.0<self.h&&p.1<self.w)}pub fn position_from(&self,b:P,offset:P)->Option<P>{let x=b.add(&offset);if self
            .is_valid_position(&x){Some(x)}else{None}}pub fn is_valid_position(&self,p:&P)->bool{p.0<self.h&&p.1<self.w}}impl<T>Index<usize>for Grid
            <T>{type Output=[T];#[inline]fn index(&self,idx:usize)->&[T]{&self.g[idx]}}impl<T>IndexMut<usize>for Grid<T>{#[inline]fn index_mut(&mut
            self,idx:usize)->&mut[T]{&mut self.g[idx]}}impl<T>Index<P>for Grid<T>{type Output=T;#[inline]fn index(&self,idx:P)->&T{&self.g[idx.0][idx
            .1]}}impl<T>IndexMut<P>for Grid<T>{#[inline]fn index_mut(&mut self,p:P)->&mut T{&mut self.g[p.0][p.1]}}}
pub mod kyopro_io {pub use crate::__cargo_equip::macros::kyopro_io::*;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_io_get{($t:ty
            )=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty
            ),*)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter=line.split_whitespace();($(iter
            .next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty;$n:expr)=>{(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*;$n:expr)=>{(0
            ..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty;;)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line
            ).unwrap();line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty;;$n:expr)=>{(0..$n).map(|_|get!($t
            ;;)).collect::<Vec<_>>()};}macro_rules!get{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_io_get!{$($tt)*})}}
pub mod kyopro_utils {pub use crate::__cargo_equip::macros::kyopro_utils::*;use std::ops::{Add,Rem}
            ;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_mat{($($e:expr),*)=>{Vec::from(vec![$($e),*])};($($e:expr,)*)=>{Vec
            ::from(vec![$($e),*])};($e:expr;$d:expr)=>{Vec::from(vec![$e;$d])};($e:expr;$d:expr$(;$ds:expr)+)=>{Vec::from(vec![mat![$e$(;$ds)*];$d])}
            ;}macro_rules!mat{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_mat!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_echo{($($num:expr),*)=>{let mut tmp=vec![];$(tmp.push(format!("{}",$num
            ));)*println!("{}",tmp.join(" "));};}macro_rules!echo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_echo!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_YesNo{($num:expr)=>{if($num)as i64==0{println!("No");}else{println!
            ("Yes");}};}macro_rules!YesNo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_YesNo!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_Yes{()=>{println!("Yes");};}macro_rules!Yes{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def_kyopro_utils_Yes!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_No{()=>{println!
            ("No");};}macro_rules!No{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_No!{$($tt)*})}pub trait SetMinMax{fn setmin(&mut self
            ,v:Self)->bool;fn setmax(&mut self,v:Self)->bool;}impl<T>SetMinMax for T where T:PartialOrd,{fn setmin(&mut self,v:T)->bool{*self>v&&{
            *self=v;true}}fn setmax(&mut self,v:T)->bool{*self<v&&{*self=v;true}}}pub fn print_vec<T>(v:&[T])where T:std::fmt::Display,{for i in 0..v
            .len(){print!("{}{}",v[i],if i+1==v.len(){""}else{" "});}println!();}pub fn pmod<T:Copy+Add<Output=T>+Rem<Output=T>>(x:T,m:T)->T{((x%m)+m
            )%m}pub fn lower_bound<T>(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>=*x{return 0;}let mut l=0;let mut r=a.len();while l+1
            <r{let m=(l+r)/2;if a[m]<*x{l=m;}else{r=m;}}r}pub fn upper_bound<T>(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>*x{return 0;}let
            mut l=0;let mut r=a.len();while l+1<r{let m=(l+r)/2;if a[m]<=*x{l=m;}else{r=m;}}r}}
}
pub(crate) mod macros {
pub mod kyopro_grid {}
pub mod kyopro_io {pub use crate::__cargo_equip_macro_def_kyopro_io_get as get;}
pub mod kyopro_utils {pub use crate::{__cargo_equip_macro_def_kyopro_utils_No as No,__cargo_equip_macro_def_kyopro_utils_Yes as Yes
            ,__cargo_equip_macro_def_kyopro_utils_YesNo as YesNo,__cargo_equip_macro_def_kyopro_utils_echo as echo
            ,__cargo_equip_macro_def_kyopro_utils_mat as mat};}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod kyopro_grid {}
pub mod kyopro_io {}
pub mod kyopro_utils {}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0