結果
| 問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
| ユーザー |
 rhoo
|
| 提出日時 | 2022-10-14 23:37:54 |
| 言語 | Rust (1.77.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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
コンパイルメッセージ
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
ソースコード
// すべての要素を読みきらないと壊れる
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);
}
}