結果

問題 No.5016 Worst Mayor
ユーザー rhoorhoo
提出日時 2023-04-29 16:16:18
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 13,327 bytes
コンパイル時間 2,533 ms
コンパイル使用メモリ 174,656 KB
実行使用メモリ 142,064 KB
スコア 17,933,609,520
平均クエリ数 32.00
最終ジャッジ日時 2023-04-29 16:18:37
合計ジャッジ時間 106,227 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,913 ms
141,464 KB
testcase_01 AC 1,926 ms
141,208 KB
testcase_02 AC 1,890 ms
141,208 KB
testcase_03 AC 1,900 ms
141,352 KB
testcase_04 AC 1,894 ms
141,432 KB
testcase_05 AC 1,907 ms
141,384 KB
testcase_06 AC 1,898 ms
141,400 KB
testcase_07 AC 1,922 ms
141,864 KB
testcase_08 AC 1,916 ms
141,940 KB
testcase_09 AC 1,899 ms
141,884 KB
testcase_10 AC 1,933 ms
141,940 KB
testcase_11 AC 1,932 ms
141,804 KB
testcase_12 TLE -
testcase_13 AC 1,922 ms
141,732 KB
testcase_14 TLE -
testcase_15 AC 1,924 ms
141,848 KB
testcase_16 AC 1,896 ms
141,212 KB
testcase_17 AC 1,905 ms
141,272 KB
testcase_18 AC 1,911 ms
141,660 KB
testcase_19 AC 1,934 ms
141,624 KB
testcase_20 AC 1,913 ms
141,872 KB
testcase_21 AC 1,959 ms
141,820 KB
testcase_22 AC 1,937 ms
141,336 KB
testcase_23 AC 1,908 ms
142,064 KB
testcase_24 AC 1,924 ms
141,820 KB
testcase_25 AC 1,933 ms
142,012 KB
testcase_26 AC 1,925 ms
141,928 KB
testcase_27 AC 1,972 ms
141,924 KB
testcase_28 AC 1,904 ms
141,816 KB
testcase_29 AC 1,925 ms
141,216 KB
testcase_30 AC 1,928 ms
141,504 KB
testcase_31 AC 1,929 ms
141,588 KB
testcase_32 AC 1,940 ms
141,836 KB
testcase_33 AC 1,900 ms
141,212 KB
testcase_34 AC 1,940 ms
141,840 KB
testcase_35 AC 1,890 ms
141,816 KB
testcase_36 AC 1,890 ms
141,768 KB
testcase_37 AC 1,880 ms
141,132 KB
testcase_38 AC 1,876 ms
141,180 KB
testcase_39 AC 1,891 ms
141,852 KB
testcase_40 AC 1,895 ms
141,596 KB
testcase_41 AC 1,914 ms
141,640 KB
testcase_42 TLE -
testcase_43 AC 1,891 ms
141,276 KB
testcase_44 TLE -
testcase_45 AC 1,863 ms
141,416 KB
testcase_46 AC 1,910 ms
141,548 KB
testcase_47 AC 1,880 ms
141,884 KB
testcase_48 AC 1,884 ms
141,224 KB
testcase_49 AC 1,859 ms
141,360 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unnecessary `unsafe` block
   --> Main.rs:377:5
    |
377 |     unsafe{
    |     ^^^^^^ unnecessary `unsafe` block
    |
    = note: `#[warn(unused_unsafe)]` on by default

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

warning: constant `DX` is never used
   --> Main.rs:530:7
    |
530 | const DX:[P;8]=[P(0,-1),P(-1,-1),P(-1,0),P(-1,1),P(0,1),P(1,1),P(1,0),P(1,-1)];
    |       ^^

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

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

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

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

warning: 7 warnings emitted

ソースコード

diff # 

#![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]),
    ];

    let mut best_ans=vec![];
    let mut best=0;
    for i in 0..4{
        let builds=make_builds(&path,i);
        let mut reach=vec![vec![false;L];L];
        for &(s,t) in &builds{
            reach[s]=true;
            reach[t]=true;
        }
        let mut builds=vec![];
        let mut que=VecDeque::new();
        que.push_back(P(7,7));
        let mut reached=vec![vec![false;L];L];
        while let Some(pos)=que.pop_front(){
            reached[pos]=true;
            for dd in DD{
                let np=pos+dd;
                if reach[np] && !reached[np]{
                    builds.push((pos,np));
                    que.push_back(np);
                }
            }
        }

        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::*;


#[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=0;
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)];
const DX:[P;8]=[P(0,-1),P(-1,-1),P(-1,0),P(-1,1),P(0,1),P(1,1),P(1,0),P(1,-1)];



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()
    }
}
0