#864710 (Rust) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: rhoo
• 提出日時: 2023-04-29 16:58:06
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 1,084 ms / 2,000 ms
• コード長: 12,731 bytes
• コンパイル時間: 3,569 ms
• コンパイル使用メモリ: 177,268 KB
• 実行使用メモリ: 100,868 KB
• スコア: 21,660,197,934
• 平均クエリ数: 400.00
• 最終ジャッジ日時: 2023-04-29 17:01:32
• 合計ジャッジ時間: 55,880 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	813 ms; 96,428 KB
testcase_01	AC	969 ms; 97,728 KB
testcase_02	AC	968 ms; 100,868 KB
testcase_03	AC	1,084 ms; 94,632 KB
testcase_04	AC	986 ms; 100,028 KB
testcase_05	AC	831 ms; 94,368 KB
testcase_06	AC	1,005 ms; 99,104 KB
testcase_07	AC	992 ms; 97,824 KB
testcase_08	AC	966 ms; 96,944 KB
testcase_09	AC	795 ms; 99,440 KB
testcase_10	AC	921 ms; 93,824 KB
testcase_11	AC	996 ms; 97,988 KB
testcase_12	AC	1,005 ms; 95,104 KB
testcase_13	AC	1,007 ms; 98,336 KB
testcase_14	AC	854 ms; 96,920 KB
testcase_15	AC	1,009 ms; 95,288 KB
testcase_16	AC	960 ms; 98,888 KB
testcase_17	AC	1,008 ms; 98,988 KB
testcase_18	AC	838 ms; 99,192 KB
testcase_19	AC	1,032 ms; 95,564 KB
testcase_20	AC	806 ms; 95,916 KB
testcase_21	AC	914 ms; 98,488 KB
testcase_22	AC	989 ms; 98,736 KB
testcase_23	AC	968 ms; 96,908 KB
testcase_24	AC	769 ms; 97,920 KB
testcase_25	AC	1,002 ms; 97,204 KB
testcase_26	AC	833 ms; 98,504 KB
testcase_27	AC	814 ms; 96,860 KB
testcase_28	AC	863 ms; 95,596 KB
testcase_29	AC	982 ms; 94,956 KB
testcase_30	AC	1,033 ms; 96,316 KB
testcase_31	AC	951 ms; 95,064 KB
testcase_32	AC	951 ms; 95,976 KB
testcase_33	AC	854 ms; 98,336 KB
testcase_34	AC	990 ms; 96,180 KB
testcase_35	AC	849 ms; 97,344 KB
testcase_36	AC	812 ms; 99,832 KB
testcase_37	AC	1,037 ms; 97,812 KB
testcase_38	AC	1,005 ms; 99,028 KB
testcase_39	AC	1,021 ms; 98,364 KB
testcase_40	AC	974 ms; 97,752 KB
testcase_41	AC	1,045 ms; 96,820 KB
testcase_42	AC	1,000 ms; 96,712 KB
testcase_43	AC	863 ms; 93,864 KB
testcase_44	AC	1,046 ms; 97,672 KB
testcase_45	AC	997 ms; 97,632 KB
testcase_46	AC	776 ms; 98,320 KB
testcase_47	AC	1,020 ms; 96,696 KB
testcase_48	AC	846 ms; 94,900 KB
testcase_49	AC	992 ms; 97,496 KB

コンパイルメッセージ

warning: unnecessary `unsafe` block
   --> Main.rs:359:5
    |
359 |     unsafe{
    |     ^^^^^^ unnecessary `unsafe` block
    |
    = note: `#[warn(unused_unsafe)]` on by default

warning: function `etime` is never used
   --> Main.rs:358:4
    |
358 | fn etime(){
    |    ^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: static `S` is never used
   --> Main.rs:330:16
    |
330 |     static mut S:usize=88172645463325252;
    |                ^

warning: function `next` is never used
   --> Main.rs:332:12
    |
332 |     pub fn next()->usize{
    |            ^^^^

warning: function `nextf` is never used
   --> Main.rs:340:12
    |
340 |     pub fn nextf()->f64{
    |            ^^^^^

warning: function `range` is never used
   --> Main.rs:344:12
    |
344 |     pub fn range(a:usize,b:usize)->usize{
    |            ^^^^^

warning: 6 warnings emitted

ソースコード

#![allow(non_snake_case)]

struct Dij{
    edge:Vec<Vec<Vec<(P,f64,bool)>>>
}
impl Dij{
    fn new()->Dij{
        let mut edge=vec![vec![vec![];L];L];
        for i in 0..L{
            for j in 0..L{
                let pos=P(i as i64,j as i64);
                for k in 0..4{
                    let np=pos+DD[k];
                    if np.in_range(){
                        edge[pos].push((np,1.,false));
                    }
                }
            }
        }

        Dij{edge}
    }

    // 一応2つのque使えばlogが消せるが、、
    fn solve(&self,start:P)->Vec<Vec<(f64,i64)>>{
        let mut que=BinaryHeap::new();
        let mut ret=vec![vec![(INFINITY,-1);L];L];
        ret[start]=(0.,0);
        que.push(S(0.,(start,0)));

        while let Some(S(dist,(pos,cnt)))=que.pop(){
            if ret[pos].0!=dist{
                continue;
            }

            for &(np,cost,f) in &self.edge[pos]{
                let nd=cost+dist;
                if nd<ret[np].0{
                    ret[np].0=nd;
                    ret[np].1=cnt+f as i64;
                    que.push(S(nd,(np,cnt+f as i64)));
                }
            }
        }

        ret
    }
}


fn solve_dp(input:&IO,builds:&[(P,P)])->(Vec<Action>,i64){
    assert!(builds.len()<=T);

    // scoresをどうにかして計算する
    let mut min_dist:Vec<_>=input.data.iter().map(|&(a,b)|((a-b).abs() as f64,0)).collect();
    let mut scores:Vec<i64>=vec![0];
    let mut grid=Dij::new();

    for &(a,b) in builds{
        let edge=&mut grid.edge[a];
        for i in 0..edge.len(){
            if edge[i].0==b{
                assert!(!edge[i].2);
                edge[i].1=C;
                edge[i].2=true;
            }
        }
        let edge=&mut grid.edge[b];
        for i in 0..edge.len(){
            if edge[i].0==a{
                assert!(!edge[i].2);
                edge[i].1=C;
                edge[i].2=true;
            }
        }

        let dists=grid.solve(a);
        for (i,&(a,b)) in input.data.iter().enumerate(){
            let dist=dists[a].0+dists[b].0;
            let cnt=dists[a].1+dists[b].1;

            if min_dist[i].0>dist{
                min_dist[i].0=dist;
                min_dist[i].1=cnt;
            }
        }

        let score:i64=min_dist.iter().map(|(_,a)|a).sum();
        scores.push(score*D);
    }

    assert_eq!(scores.len(),builds.len()+1);

    const INF:i64=std::i64::MAX/4;

    const MAX_PEOPLE:usize=101;
    // DP[t][i][j]:=tターンで人がi人いてjまで建設が終わっているときの最大の金
    let mut dp0=vec![vec![(-INF,Rc::new(Nil));builds.len()+1];MAX_PEOPLE];
    dp0[1][0].0=INIT_MONEY;

    for _ in 1..=T{
        let mut dp1=vec![vec![(-INF,Rc::new(Nil));builds.len()+1];MAX_PEOPLE];
        for j in 0..MAX_PEOPLE{
            for k in 0..=builds.len(){
                // 建設する
                if k!=builds.len() && j!=0{
                    let new=dp0[j][k].0-(1e7/(j as f64).sqrt()) as i64;
                    if new>=0{
                        let new=new+scores[k+1];
                        if dp1[j][k+1].0<new{
                            dp1[j][k+1]=(new,Rc::new(Cons{v:Build(builds[k]),prev:dp0[j][k].1.clone()}));
                        }
                    }
                }
                
                // 協力者を集める
                if j!=MAX_PEOPLE-1{
                    let new=dp0[j][k].0+scores[k];
                    if dp1[j+1][k].0<new{
                        dp1[j+1][k]=(dp0[j][k].0,Rc::new(Cons{v:People,prev:dp0[j][k].1.clone()}));
                    }
                }
                
                // 資金集めをする
                let new=dp0[j][k].0+MONEY+scores[k];
                if dp1[j][k].0<new{
                    dp1[j][k]=(new,Rc::new(Cons{v:Money,prev:dp0[j][k].1.clone()}));
                }
            }
        }

        std::mem::swap(&mut dp0,&mut dp1);
    }

    let mut best=0;
    let mut arg=Rc::new(Nil);
    for i in 0..MAX_PEOPLE{
        for j in 0..=builds.len(){
            if dp0[i][j].0>best{
                best=dp0[i][j].0;
                arg=dp0[i][j].1.clone();
            }
        }
    }

    (arg.restore(),best)
}


fn connect(mut s:P,t:P,builds:&mut Vec<(P,P)>){
    'outer: while s!=t{
        for dd in DD{
            let ns=s+dd;
            if (s-t).abs()>(ns-t).abs(){
                builds.push((s,ns));
                s=ns;
                continue 'outer;
            }
        }
        panic!();
    }
}

fn make_builds(points:&[(P,P)],rot:usize)->Vec<(P,P)>{
    let mut ret=vec![];
    for &(mut s,mut t) in points{
        for _ in 0..rot{
            s=s.rot();
            t=t.rot();
        }
        connect(s,t,&mut ret);
    }
    ret
}


fn solve(input:&IO)->Vec<Action>{
    let a=[2,7,12];
    let b=[2,5,8,11];

    let mut pos=vec![vec![P(0,0);b.len()];a.len()];
    for i in 0..a.len(){
        for j in 0..b.len(){
            pos[i][j]=P(a[i],b[j]);
        }
    }

    let path=vec![
        (pos[1][1],pos[1][2]),
        (pos[1][1],pos[2][1]),
        (pos[1][2],pos[0][2]),
        (pos[2][1],pos[2][0]),
        (pos[0][2],pos[0][3]),
        (pos[2][0],pos[0][0]),
        (pos[0][3],pos[2][3]),
        (pos[0][0],pos[0][1]),
        (pos[2][3],pos[2][1])
    ];

    let mut best_ans=vec![];
    let mut best=0;
    for i in 0..1{
        let builds=make_builds(&path,i);
        let (ans,score)=solve_dp(input,&builds);
        if best<score{
            best=score;
            best_ans=ans;
        }
    }
    eprintln!("score = {}",best);

    let mut seen=vec![vec![false;L];L];
    for &act in &best_ans{
        if let Build((s,t))=act{
            seen[s]=true;
            seen[t]=true;
        }
    }

    eprintln!();
    for i in 0..L{
        for j in 0..L{
            if seen[i][j]{
                eprint!("#");
            }
            else{
                eprint!(".");
            }
        }
        eprintln!();
    }

    best_ans
}


fn main(){
    let IO=IO::input();
    let ans=solve(&IO);
    IO.output(&ans);
}


use std::f64::INFINITY;
use std::collections::BinaryHeap;


#[derive(Clone,Copy,PartialEq,Eq,Debug)]
enum Action{
    Build((P,P)),
    People,
    Money
}
use Action::*;


const N:usize=3000;
const T:usize=400;
const C:f64=0.223;
const INIT_MONEY:i64=1e6 as i64;
const MONEY:i64=50000;
const L:usize=14;
const D:i64=60;


struct IO{
    scan:Scanner,
    data:[(P,P);N]
}
impl IO{
    fn input()->IO{
        let mut scan=Scanner::new();
        input!{
            scan,
            n:usize,
            t:usize,
            d:[((Usize1,Usize1),(Usize1,Usize1));N]
        }
        assert_eq!((n,t),(N,T));

        let data=d.into_iter().map(|((a,b),(c,d))|(P(a as i64,b as i64),P(c as i64,d as i64))).collect::<Vec<_>>();
        IO{scan,data:data.try_into().unwrap()}
    }

    fn output(self,ans:&[Action]){
        assert_eq!(ans.len(),T);
        let mut scan=self.scan;
        for &act in ans{
            #[cfg(not(local))]{
                input!{
                    scan,
                    _u:usize,
                    _v:usize,
                }
            }
            
            match act{
                Build((P(a,b),P(c,d)))=>println!("1 {} {} {} {}",a+1,b+1,c+1,d+1),
                People=>println!("2"),
                Money=>println!("3")
            }
        }
    }
}


#[macro_export]#[cfg(not(local))]macro_rules! eprint{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}


fn get_time()->f64{
    static mut START:f64=-1.;
    let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
    unsafe{
        if START<0.{
            START=time;
        }

        #[cfg(local)]{
            (time-START)*1.6
        }
        #[cfg(not(local))]{
            time-START
        }
    }
}


mod rnd {
    static mut S:usize=88172645463325252;
    
    pub fn next()->usize{
        unsafe{
            S^=S<<7;
            S^=S>>9;
            S
        }
    }

    pub fn nextf()->f64{
        f64::from_bits((0x3ff0000000000000|next()&0xfffffffffffff) as u64)-1.
    }

    pub fn range(a:usize,b:usize)->usize{
        next()%(b-a)+a
    }
}


#[macro_export]
macro_rules! timer{
    ()=>{
        let _timer=Timer(get_time());
    }
}

static mut TIME:f64=0.;
fn etime(){
    unsafe{
        eprintln!("{:.3}",TIME);
    }
}

struct Timer(f64);
impl Drop for Timer{
    fn drop(&mut self){
        unsafe{
            TIME+=get_time()-self.0
        }
    }
}


struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
impl Scanner{
    fn new()->Self{
        Self{stack:"".split_ascii_whitespace()}
    }

    fn read<T:std::str::FromStr>(&mut self)->T{
        loop{
            if let Some(v)=self.stack.next(){
                return v.parse::<T>().unwrap_or_else(|_|panic!("{}: parse error",std::any::type_name::<T>()));
            }

            let mut tmp=String::new();
            std::io::stdin().read_line(&mut tmp).unwrap();
            assert!(!tmp.is_empty());
            self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
        }
    }
}

#[macro_export]
macro_rules! input{
    ($scan:ident, $($rest:tt)*)=>{
        input_inner!{$scan,$($rest)*}
    };
}

#[macro_export]
macro_rules! input_inner{
    ($scan:ident $(,)?)=>{};
    ($scan:ident, $name:ident:$t:tt $($rest:tt)*)=>{
        let $name=read_value!($scan,$t);
        input_inner!{$scan $($rest)*}
    };
}

#[macro_export]
macro_rules! read_value{
    ($scan:ident, ($($t:tt),*))=>{
        ($(read_value!($scan, $t)),*)
    };
    ($scan:ident, [$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:ident, Chars)=>{
        read_value!($scan,String).chars().collect::<Vec<char>>()
    };
    ($scan:ident, Usize1)=>{
        read_value!($scan,usize)-1
    };
    ($scan:ident, $t:ty)=>{
        $scan.read::<$t>()
    };
}


#[derive(Clone,Copy,PartialEq,Eq,Debug,Default,Hash)]
struct P(i64,i64);
impl P{
    fn in_range(self)->bool{
        L>self.0 as usize && L>self.1 as usize
    }

    fn abs(self)->i64{
        self.0.abs()+self.1.abs()
    }

    fn rot(self)->P{
        P(self.1,L as i64-self.0)
    }
}
use std::ops::*;
impl Add for P{
    type Output=P;
    fn add(self,a:P)->P{
        P(self.0+a.0,self.1+a.1)
    }
}
impl Sub for P{
    type Output=P;
    fn sub(self,a:P)->P{
        P(self.0-a.0,self.1-a.1)
    }
}
impl Mul<i64> for P{
    type Output=P;
    fn mul(self,a:i64)->P{
        P(self.0*a,self.1*a)
    }
}
impl Div<i64> for P{
    type Output=P;
    fn div(self,a:i64)->P{
        P(self.0/a,self.1/a)
    }
}
impl Neg for P{
    type Output=P;
    fn neg(self)->P{
        P(-self.0,-self.1)
    }
}
impl AddAssign for P{
    fn add_assign(&mut self,a:P){
        *self=*self+a;
    }
}
impl SubAssign for P{
    fn sub_assign(&mut self,a:P){
        *self=*self-a;
    }
}
impl MulAssign<i64> for P{
    fn mul_assign(&mut self,a:i64){
        *self=*self*a;
    }
}
impl DivAssign<i64> for P{
    fn div_assign(&mut self,a:i64){
        *self=*self/a;
    }
}
impl<T:Index<usize>> Index<P> for Vec<T>{
    type Output=T::Output;
    fn index(&self,idx:P)->&T::Output{
        &self[idx.0 as usize][idx.1 as usize]
    }
}
impl<T:IndexMut<usize>> IndexMut<P> for Vec<T>{
    fn index_mut(&mut self,idx:P)->&mut T::Output{
        &mut self[idx.0 as usize][idx.1 as usize]
    }
}


const DD:[P;4]=[P(0,-1),P(-1,0),P(0,1),P(1,0)];



use std::rc::Rc;
#[derive(Clone)]
enum List<T>{
    Cons{
        v:T,
        prev:Rc<List<T>>
    },
    Nil
}
use List::*;
impl<T:Clone> List<T>{
    fn restore(&self)->Vec<T>{
        let mut ret=vec![];
        let mut ptr=self.clone();

        while let Cons{v,prev}=ptr{
            ret.push(v.clone());
            ptr=(*prev).clone();
        }

        ret.reverse();
        ret
    }
}


#[derive(PartialEq,PartialOrd)]
struct O<T:PartialEq+PartialOrd>(T);
impl<T:PartialEq+PartialOrd> Eq for O<T>{} 
impl<T:PartialEq+PartialOrd> Ord for O<T>{
    fn cmp(&self,a:&O<T>)->std::cmp::Ordering{
        self.0.partial_cmp(&a.0).unwrap()
    }
}


struct S<T:PartialEq+PartialOrd,U>(T,U);
impl<T:PartialEq+PartialOrd,U> PartialEq for S<T,U>{
    fn eq(&self,a:&S<T,U>)->bool{
        self.0.eq(&a.0)
    }
}
impl<T:PartialEq+PartialOrd,U> PartialOrd for S<T,U>{
    fn partial_cmp(&self,a:&S<T,U>)->Option<std::cmp::Ordering>{
        self.0.partial_cmp(&a.0)
    }
}
impl<T:PartialEq+PartialOrd,U> Eq for S<T,U>{}
impl<T:PartialEq+PartialOrd,U> Ord for S<T,U>{
    fn cmp(&self,a:&S<T,U>)->std::cmp::Ordering{
        self.partial_cmp(a).unwrap()
    }
}