結果

問題 No.5016 Worst Mayor
ユーザー rhoorhoo
提出日時 2023-04-29 15:26:45
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 403 ms / 2,000 ms
コード長 12,176 bytes
コンパイル時間 2,433 ms
コンパイル使用メモリ 172,520 KB
実行使用メモリ 110,196 KB
スコア 16,613,307,960
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 15:27:20
合計ジャッジ時間 24,122 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 357 ms
110,196 KB
testcase_01 AC 359 ms
109,672 KB
testcase_02 AC 353 ms
109,864 KB
testcase_03 AC 356 ms
109,984 KB
testcase_04 AC 358 ms
109,596 KB
testcase_05 AC 403 ms
109,684 KB
testcase_06 AC 357 ms
109,988 KB
testcase_07 AC 360 ms
109,492 KB
testcase_08 AC 354 ms
109,912 KB
testcase_09 AC 358 ms
109,552 KB
testcase_10 AC 382 ms
109,808 KB
testcase_11 AC 354 ms
109,588 KB
testcase_12 AC 353 ms
109,556 KB
testcase_13 AC 363 ms
109,920 KB
testcase_14 AC 363 ms
109,684 KB
testcase_15 AC 360 ms
109,584 KB
testcase_16 AC 352 ms
109,772 KB
testcase_17 AC 378 ms
109,864 KB
testcase_18 AC 356 ms
109,600 KB
testcase_19 AC 357 ms
109,848 KB
testcase_20 AC 382 ms
110,068 KB
testcase_21 AC 357 ms
110,076 KB
testcase_22 AC 353 ms
109,700 KB
testcase_23 AC 354 ms
109,976 KB
testcase_24 AC 353 ms
110,068 KB
testcase_25 AC 358 ms
109,768 KB
testcase_26 AC 355 ms
109,684 KB
testcase_27 AC 358 ms
110,196 KB
testcase_28 AC 362 ms
109,760 KB
testcase_29 AC 356 ms
110,124 KB
testcase_30 AC 357 ms
109,568 KB
testcase_31 AC 356 ms
109,848 KB
testcase_32 AC 357 ms
109,756 KB
testcase_33 AC 350 ms
109,900 KB
testcase_34 AC 354 ms
110,036 KB
testcase_35 AC 353 ms
109,496 KB
testcase_36 AC 355 ms
109,772 KB
testcase_37 AC 355 ms
109,768 KB
testcase_38 AC 360 ms
110,192 KB
testcase_39 AC 358 ms
109,564 KB
testcase_40 AC 357 ms
109,932 KB
testcase_41 AC 351 ms
110,096 KB
testcase_42 AC 361 ms
109,808 KB
testcase_43 AC 352 ms
109,792 KB
testcase_44 AC 360 ms
110,020 KB
testcase_45 AC 360 ms
109,712 KB
testcase_46 AC 358 ms
110,140 KB
testcase_47 AC 357 ms
109,792 KB
testcase_48 AC 355 ms
109,696 KB
testcase_49 AC 356 ms
110,112 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `debug` is assigned to, but never used
   --> Main.rs:137:13
    |
137 |     let mut debug=(0,0);
    |             ^^^^^
    |
    = note: consider using `_debug` instead
    = note: `#[warn(unused_variables)]` on by default

warning: value assigned to `debug` is never read
   --> Main.rs:143:17
    |
143 |                 debug=(i,j);
    |                 ^^^^^
    |
    = help: maybe it is overwritten before being read?
    = note: `#[warn(unused_assignments)]` on by default

warning: unused variable: `input`
   --> Main.rs:155:12
    |
155 | fn sa_path(input:&IO)->Vec<P>{
    |            ^^^^^ help: if this is intentional, prefix it with an underscore: `_input`

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

warning: function `sa_path` is never used
   --> Main.rs:155:4
    |
155 | fn sa_path(input:&IO)->Vec<P>{
    |    ^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function `etime` is never used
   --> Main.rs:331:4
    |
331 | fn etime(){
    |    ^^^^^

warning: constant `DX` is never used
   --> Main.rs:481:7
    |
481 | 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:303:16
    |
303 |     static mut S:usize=88172645463325252;
    |                ^

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

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

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

warning: 11 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>{
    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);
    let mut debug=(0,0);
    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();
                debug=(i,j);
            }
        }
    }

    eprintln!("best = {}",best);
    eprintln!("debug = {:?}",debug);

    arg.restore()
}


fn sa_path(input:&IO)->Vec<P>{
    todo!();
}


fn solve(input:&IO)->Vec<Action>{
    let mut builds=vec![];

    let s=4;
    let t=9;
    for i in s..t{
        builds.push((P(8,i),P(8,i+1)));
    }
    builds.push((P(7,s),P(8,s)));
    builds.push((P(7,s),P(6,s)));
    builds.push((P(5,s),P(6,s)));
    for i in s..t{
        builds.push((P(5,i),P(5,i+1)));
    }
    builds.push((P(5,t),P(4,t)));
    builds.push((P(3,t),P(4,t)));
    builds.push((P(3,t),P(2,t)));
    builds.push((P(8,t),P(9,t)));
    builds.push((P(10,t),P(9,t)));
    builds.push((P(10,t),P(11,t)));
    for i in (s..t).rev(){
        builds.push((P(11,i),P(11,i+1)));
    }
    for i in (s..t).rev(){
        builds.push((P(2,i),P(2,i+1)));
    }

    let mut seen=vec![vec![false;L];L];
    for &(s,t) in &builds{
        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!();
    }

    solve_dp(input,&builds)
}


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