結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー rhoo
提出日時 2022-10-14 23:37:54
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 11,027 bytes
コンパイル時間 1,313 ms
実行使用メモリ 6,956 KB
スコア 0
最終ジャッジ日時 2022-10-14 23:39:04
合計ジャッジ時間 52,525 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge10
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused macro definition: `debug`
   --> Main.rs:134:14
    |
134 | macro_rules! debug{
    |              ^^^^^
    |
    = note: `#[warn(unused_macros)]` on by default

warning: unused variable: `score`
   --> Main.rs:512:13
    |
512 |     let mut score=cur.score();
    |             ^^^^^ help: if this is intentional, prefix it with an underscore: `_score`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> Main.rs:511:9
    |
511 |     let mut cur=Out::new(gen_cands(input));
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> Main.rs:512:9
    |
512 |     let mut score=cur.score();
    |         ----^^^^^
    |         |
    |         help: remove this `mut`

warning: associated function is never used: `del`
   --> Main.rs:252:8
    |
252 |     fn del(&mut self,a:usize){
    |        ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: associated function is never used: `rand`
   --> Main.rs:262:8
    |
262 |     fn rand(&self)->usize{
    |        ^^^^

warning: associated function is never used: `nto_slice`
   --> Main.rs:277:8
    |
277 |     fn nto_slice(&self)->&[usize]{
    |        ^^^^^^^^^

warning: associated function is never used: `contains`
   --> Main.rs:282:8
    |
282 |     fn contains(&self,v:usize)->bool{
    |        ^^^^^^^^

warning: associated function is never used: `is_empty`
   --> Main.rs:287:8
    |
287 |     fn is_empty(&self)->bool{
    |        ^^^^^^^^

warning: associated function is never used: `clear`
   --> Main.rs:292:8
    |
292 |     fn clear(&mut self){
    |        ^^^^^

warning: associated function is never used: `fill`
   --> Main.rs:297:8
    |
297 |     fn fill(&mut self){
    |        ^^^^

warning: associated function is never used: `swap`
   --> Main.rs:460:8
    |
460 |     fn swap(&mut self,a:usize,b

ソースコード

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

// すべての要素を読みきらないと壊れる
macro_rules! input{
    ($($rest:tt)*)=>{
        let mut stack="".split_ascii_whitespace();
        let mut next=move ||->&str{
            loop{
                if let Some(v)=stack.next(){
                    return v;
                }
 
                let mut tmp=String::new();
                std::io::stdin().read_line(&mut tmp).unwrap();
                if tmp.is_empty(){
                    panic!("reached the end");
                }
                else{
                    stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
                }
            }
        };
 
        input_inner!{next,$($rest)*}
    };
}
 
macro_rules! input_inner{
    ($next:ident $(,)?)=>{};
    ($next:ident, $name:ident:$t:tt $($rest:tt)*)=>{
        let $name=read_value!($next,$t);
        input_inner!{$next $($rest)*}
    };
}
 
macro_rules! read_value{
    ($next:ident, ($($t:tt),*))=>{
        ($(read_value!($next, $t)),*)
    };
    ($next:ident, [$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($next,$t)).collect::<Vec<_>>()
    };
    ($next:ident, Chars)=>{
        read_value!($next,String).chars().collect::<Vec<char>>()
    };
    ($next:ident, Usize1)=>{
        read_value!($next,usize)-1
    };
    ($next:ident, $t:ty)=>{
        $next().parse::<$t>().expect("parse error")
    };
}
#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    #[inline]
    pub fn next()->usize{
        unsafe{
            S^=S<<7;
            S^=S>>9;
            S
        }
    }
    
    #[inline]
    pub fn nextf()->f64{
        unsafe{
            std::mem::transmute::<_,f64>(0x3ff0000000000000|next()&0xfffffffffffff)-1.
        }
    }
    
    #[inline]
    pub fn range(a:usize,b:usize)->usize{
        next()%(b-a)+a
    }
    
    #[inline]
    pub fn exu(a:usize,b:usize,skip:usize)->usize{
        let ret=range(a,b-1);
        if ret==skip{b-1}
        else{ret}
    }
    #[inline]
    pub fn rangei(a:i64,b:i64)->i64{
        (next()>>1) as i64%(b-a)+a
    }
    #[inline]
    pub fn exi(a:i64,b:i64,skip:i64)->i64{
        let ret=rangei(a,b-1);
        if ret==skip{b-1}
        else{ret}
    }
}
#[allow(unused)]
#[inline]
fn get_time()->f64{
    static mut START:f64=-1.;
    let t=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
    unsafe{
        if START<0.{START=t;}
        t-START
    }
}
#[cfg(local)]
#[allow(unused)]
macro_rules! debug{
    ()=>{
        eprintln!();
    };
    ($x:literal)=>{
        eprintln!("{:?}",$x);
    };
    ($x:expr)=>{
        eprintln!("{}: {:?}",stringify!($x),$x);
    };
    ($x:literal,$($l:expr),*)=>{
        eprint!("{:?}, ",$x);
        debug!($($l),*);
    };
    ($x:expr,$($l:expr),*)=>{
        eprint!("{}: {:?}, ",stringify!($x),$x);
        debug!($($l),*);
    }
}
#[cfg(not(local))]
macro_rules! debug{
    ($($_:tt)*)=>{}
}
#[cfg(local)]
macro_rules! log{
    ()=>{};
    ($x:literal)=>{
        eprintln!("{}",$x);
    };
    
    ($x:ident $(,)?)=>{
        log!(@out $x,$x);
    };
    ($x:ident,$t:ident $(,)?)=>{
        log!(@out $x,$x);
        log!($t);
    };
    ($x:ident,$($_:ident).* $(,)?)=>{
        compile_error!();
    };
    ($x:ident,$t:expr $(,)?)=>{
        log!(@out $x,$t);
    };
    ($($x:ident).* $(,)?)=>{
        log!(@last $($x).*;$($x).*);
    };
    ($x:ident,$t:ident,$($rest:tt)*)=>{
        log!(@out $x,$x);
        log!($t,$($rest)*);
    };
    ($x:ident,$($_:ident).*,$($rest:tt)*)=>{
        compile_error!();
    };
    ($x:ident,$t:expr,$($rest:tt)*)=>{
        log!(@out $x,$t);
        log!($($rest)*);
    };
    ($($x:ident).*,$($rest:tt)*)=>{
        log!(@last $($x).*;$($x).*);
        log!($($rest)*);
    };
    (@out $x:ident,$t:expr)=>{
        eprintln!("{} = {:?}",stringify!($x),$t);
    };
    (@last $x:ident;$full:expr)=>{
        log!(@out $x,$full);
    };
    (@last $_:ident. $($rest:ident).*;$full:expr)=>{
        log!(@last $($rest).*;$full)
    }
}
#[cfg(not(local))]
macro_rules! log{
    ($($_:tt)*)=>{}
}
macro_rules! param{
    ($($x:ident:$t:ty=$v:literal),* $(,)?)=>{
        #[allow(non_snake_case)]
        struct Param{
            $($x:$t),*
        }
        impl Param{
            #[inline]
            fn new()->Self{
                Self{
                    $(
                        $x:match std::env::var(stringify!($x)){
                            Ok(s)=>s.parse().expect("parse error"),
                            Err(_)=>$v
                        }
                    ),*
                }
            }
        }
    };
}
const N:usize=50;
const K:usize=50;
#[derive(Clone)]
struct IndexSet{
    pos:Vec<usize>,
    que:Vec<usize>,
    len:usize
}
impl IndexSet{
    #[inline]
    fn new(n:usize)->IndexSet{
        IndexSet{
            pos:(0..n).collect::<Vec<_>>(),
            que:(0..n).collect::<Vec<_>>(),
            len:0
        }
    }
    #[inline]
    fn add(&mut self,a:usize){
        let p=self.pos[a];
        assert!(self.len<=p);
        self.que.swap(p,self.len);
        self.pos.swap(a,self.que[p]);
        self.len+=1;
    }
    #[inline]
    fn del(&mut self,a:usize){
        let p=self.pos[a];
        assert!(p<self.len);
        self.que.swap(p,self.len-1);
        self.pos.swap(a,self.que[p]);
        self.len-=1;
    }
    #[inline]
    fn rand(&self)->usize{
        self.que[rnd::next()%self.len]
    }
    #[inline]
    fn nrand(&self)->usize{
        self.que[rnd::range(self.len,self.que.len())]
    }
    #[inline]
    fn to_slice(&self)->&[usize]{
        &self.que[..self.len]
    }
    #[inline]
    fn nto_slice(&self)->&[usize]{
        &self.que[self.len..]
    }
    
    #[inline]
    fn contains(&self,v:usize)->bool{
        self.pos[v]<self.len
    }
    #[inline]
    fn is_empty(&self)->bool{
        self.len==0
    }
    #[inline]
    fn clear(&mut self){
        self.len=0;
    }
    #[inline]
    fn fill(&mut self){
        self.len=self.pos.len();
    }
}
struct In{
    t:Vec<i64>,
    u:Vec<i64>,
    param:Param
}
impl In{
    #[inline]
    fn input()->In{
        input!{
            n:usize,
            k:usize,
            t:[i64;K],
            u:[i64;K]
        }
        assert_eq!((n,k),(N,K));
        In{
            t,u,
            param:Param::new()
        }
    }
}
struct Pen{
    b:i64,
    m:i64,
    e:i64,
    tn:i64,
    t:i64,
    tp:[i64;K],
    up:[i64;K]
}
impl Pen{
    #[inline]
    fn new(b:i64,m:i64,e:i64)->Pen{
        let tn=1+(b-m)/e;
        let t=tn*(2*b-e*(tn-1));
        Pen{b,m,e,tn,t,tp:[-1;K],up:[-1;K]}
    }
    #[inline]
    fn get_time(&self,n:i64)->i64{
        if n<=self.tn{
            n*(2*self.b-self.e*(n-1))
        }
        else{
            self.t+2*self.m*(n-self.tn)
        }
    }
    #[inline]
    fn get_h(&self,n:i64)->i64{
        if n<=self.tn{
            self.b-n*self.e
        }
        else{
            self.m
        }
    }
    #[inline]
    fn get_pos(&self,t:i64,mut ok:i64,mut ng:i64)->i64{
        while ng-ok>1{
            let m=(ok+ng)/2;
            if self.get_time(m)<=t{
                ok=m;
            }
            else{
                ng=m;
            }
        }
        let rest=t-self.get_time(ok);
        let h=self.get_h(ok);
        rest.min(2*h-rest)*(1-2*(ok&1))
    }
    #[inline]
    fn calc_conf(&mut self,input:&In){
        let mut prev=0;
        for i in 0..K{
            self.tp[i]=self.get_pos(input.t[i],prev,input.t[i]+1);
            prev=self.tp[i];
        }
    }
    #[inline]
    fn calc_coop(&mut self,input:&In){
        let mut prev=0;
        for i in 0..K{
            self.up[i]=self.get_pos(input.u[i],prev,input.u[i]+1);
            prev=self.up[i];
        }
    }
}
struct Out{
    cands:Vec<Pen>,
    set:IndexSet
}
impl Out{
    #[inline]
    fn new(cands:Vec<Pen>)->Out{
        let mut set=IndexSet::new(cands.len());
        for _ in 0..N{
            set.add(set.nrand());
        }
        Out{cands,set}
    }
    #[inline]
    fn score(&self)->i128{
        let conf=|idx:usize|->i128{
            let mut sum=0.;
            for i in 0..N-1{
                let bi=self.cands[self.set.que[i]].b;
                let xi=self.cands[self.set.que[i]].tp[idx];
                for j in i+1..N{
                    let bj=self.cands[self.set.que[j]].b;
                    let xj=self.cands[self.set.que[j]].tp[idx];
                    sum+=(xi-xj).abs() as f64/(bi+bj) as f64;
                }
            }
            (sum*2e7/(N*(N-1)) as f64).round() as i128
        };
        let coop=|idx:usize|->i128{
            let mut max=0;
            for i in 0..N-1{
                let xi=self.cands[self.set.que[i]].up[idx];
                for j in i+1..N{
                    let xj=self.cands[self.set.que[j]].up[idx];
                    max=max.max((xi-xj).abs());
                }
            }
            (1e7/((max as f64/20.)+1.).sqrt()).round() as i128
        };
        let mut av_conf=0;
        let mut av_coop=0;
        for i in 0..K{
            av_conf+=conf(i);
            av_coop+=coop(i);
        }
        av_conf=(av_conf as f64/K as f64).round() as i128;
        av_coop=(av_coop as f64/K as f64).round() as i128;
        av_conf*av_coop
    }
    #[inline]
    fn swap(&mut self,a:usize,b:usize){
        self.set.del(a);
        self.set.add(b);
    }
}
#[inline]
fn score(input:&In,pen:&mut Pen)->i128{
    pen.calc_coop(input);
    pen.up.iter().map(|&v|(v as i128*v as i128)).sum::<i128>()
}
fn gen_cands(input:&In)->Vec<Pen>{
    let BL=input.param.MAXB as usize/input.param.O;
    let EL=input.param.MAXE as usize/input.param.O;
    let mut ret=vec![];
    let mut stack=vec![];
    for e in 0..EL{
        let mine=e*input.param.O+1;
        let maxe=mine+input.param.O+1;
        for b in 0..BL{
            let minb=b*input.param.O+1;
            let maxb=minb+input.param.O+1;
            stack.clear();
            for _ in 0..input.param.T{
                // bme
                let mut pen=Pen::new(rnd::range(minb,maxb) as i64,rnd::range(1,input.param.MAXM as usize) as i64,rnd::range(mine,maxe) as i64);
                let score=score(input,&mut pen);
                stack.push((pen,score));
            }
            stack.sort_unstable_by_key(|(_,score)|*score);
            stack.truncate(input.param.NTH);
            while let Some((mut pen,_))=stack.pop(){
                pen.calc_conf(input);
                ret.push(pen);
            }
        }
    }
    ret
}
fn sa(input:&In)->Out{
    let mut cur=Out::new(gen_cands(input));
    let mut score=cur.score();
    log!(score);
    cur
}
param!{
    MAXB:i64=2000,
    MAXM:i64=2000,
    MAXE:i64=100,
    T:usize=1000,
    NTH:usize=30,
    O:usize=40,
}
fn main(){
    let input=In::input();
    let ans=sa(&input);
    for &i in ans.set.to_slice(){
        let Pen{b,m,e,..}=ans.cands[i];
        println!("{} {} {}",b,m,e);
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0