// すべての要素を読みきらないと壊れる 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); } }