結果
| 問題 |
No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
|
| コンテスト | |
| ユーザー |
 ntk-ta01
|
| 提出日時 | 2022-10-15 01:18:55 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 18,181 bytes |
| コンパイル時間 | 994 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 123,963,296,286,695 |
| 最終ジャッジ日時 | 2022-10-15 01:19:44 |
| 合計ジャッジ時間 | 8,602 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: unused import: `ntk_rand::Xorshift`
--> Main.rs:51:5
|
51 | use ntk_rand::Xorshift;
| ^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused variable: `t`
--> Main.rs:57:9
|
57 | t: [usize; k],
| ^ help: if this is intentional, prefix it with an underscore: `_t`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `u`
--> Main.rs:58:9
|
58 | u: [usize; k],
| ^ help: if this is intentional, prefix it with an underscore: `_u`
warning: struct is never constructed: `Timer`
--> Main.rs:76:8
|
76 | struct Timer {
| ^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: associated function is never used: `new`
--> Main.rs:81:8
|
81 | fn new() -> Timer {
| ^^^
warning: associated function is never used: `get_time`
--> Main.rs:87:8
|
87 | fn get_time(&self) -> f64 {
| ^^^^^^^^
warning: 6 warnings emitted
ソースコード
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
use ntk_rand::Xorshift;
fn main() {
input! {
n: usize,
k: usize,
t: [usize; k],
u: [usize; k],
}
let mut rng = ntk_rand::Xorshift::new();
for _ in 0..n {
let b = rng.gen_range(0..1000);
let m = (b as f64 * 0.32) as usize;
let e = (m as f64 * rng.gen_range(1..4) as f64 * 0.15) as usize;
println!("{} {} {}", b, m, e);
}
}
pub fn get_time() -> f64 {
let t = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap();
t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9
}
struct Timer {
start_time: f64,
}
impl Timer {
fn new() -> Timer {
Timer {
start_time: get_time(),
}
}
fn get_time(&self) -> f64 {
get_time() - self.start_time
}
}
#[allow(dead_code)]
mod ntk_rand {
pub trait Distribution<T, TX> {
/// Generate a random value of `T`, using `rng` as the source of randomness.
fn sample(&self, rng: &mut Xorshift<TX>) -> T;
}
pub struct Xorshift<T> {
seed: T,
}
impl Xorshift<usize> {
pub fn new() -> Self {
Xorshift {
seed: 0x139408dcbbf7a44,
}
}
pub fn seed_from_u64(seed: usize) -> Xorshift<usize> {
Xorshift { seed }
}
fn gen(&mut self) -> usize {
self.seed = self.seed ^ (self.seed << 13);
self.seed = self.seed ^ (self.seed >> 7);
self.seed = self.seed ^ (self.seed << 17);
self.seed
}
pub fn rand(&mut self) -> usize {
self.gen()
}
fn sample<T, D: Distribution<T, usize>>(&mut self, distr: D) -> T {
distr.sample(self)
}
pub fn gen_bool(&mut self, p: f64) -> bool {
let d = Bernoulli::new(p).unwrap();
self.sample(d)
}
pub fn gen_range<T, R>(&mut self, range: R) -> T
where
T: SampleUniform,
R: SampleRange<T>,
{
range.sample_single(self)
}
}
pub struct Uniform<X: SampleUniform>(X::Sampler);
impl<X: SampleUniform> Uniform<X> {
pub fn new<B1, B2>(low: B1, high: B2) -> Uniform<X>
where
B1: SampleBorrow<X> + Sized,
B2: SampleBorrow<X> + Sized,
{
Uniform(X::Sampler::new(low, high))
}
pub fn new_inclusive<B1, B2>(low: B1, high: B2) -> Uniform<X>
where
B1: SampleBorrow<X> + Sized,
B2: SampleBorrow<X> + Sized,
{
Uniform(X::Sampler::new_inclusive(low, high))
}
}
impl<X: SampleUniform> Distribution<X, usize> for Uniform<X> {
fn sample(&self, rng: &mut Xorshift<usize>) -> X {
self.0.sample(rng)
}
}
pub trait UniformSampler: Sized {
/// The type sampled by this implementation.
type X;
fn new<B1, B2>(low: B1, high: B2) -> Self
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized;
fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized;
/// Sample a value.
fn sample(&self, rng: &mut Xorshift<usize>) -> Self::X;
fn sample_single<B1, B2>(low: B1, high: B2, rng: &mut Xorshift<usize>) -> Self::X
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized,
{
let uniform: Self = UniformSampler::new(low, high);
uniform.sample(rng)
}
fn sample_single_inclusive<B1, B2>(low: B1, high: B2, rng: &mut Xorshift<usize>) -> Self::X
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized,
{
let uniform: Self = UniformSampler::new_inclusive(low, high);
uniform.sample(rng)
}
}
impl<X: SampleUniform> From<core::ops::Range<X>> for Uniform<X> {
fn from(r: core::ops::Range<X>) -> Uniform<X> {
Uniform::new(r.start, r.end)
}
}
impl<X: SampleUniform> From<core::ops::RangeInclusive<X>> for Uniform<X> {
fn from(r: core::ops::RangeInclusive<X>) -> Uniform<X> {
Uniform::new_inclusive(r.start(), r.end())
}
}
pub trait SampleUniform: Sized {
/// The `UniformSampler` implementation supporting type `X`.
type Sampler: UniformSampler<X = Self>;
}
pub trait SampleBorrow<Borrowed> {
/// Immutably borrows from an owned value. See [`Borrow::borrow`]
///
/// [`Borrow::borrow`]: std::borrow::Borrow::borrow
fn borrow(&self) -> &Borrowed;
}
impl<Borrowed> SampleBorrow<Borrowed> for Borrowed
where
Borrowed: SampleUniform,
{
#[inline(always)]
fn borrow(&self) -> &Borrowed {
self
}
}
impl<'a, Borrowed> SampleBorrow<Borrowed> for &'a Borrowed
where
Borrowed: SampleUniform,
{
#[inline(always)]
fn borrow(&self) -> &Borrowed {
*self
}
}
/// Range that supports generating a single sample efficiently.
///
/// Any type implementing this trait can be used to specify the sampled range
/// for `Rng::gen_range`.
pub trait SampleRange<T> {
/// Generate a sample from the given range.
fn sample_single(self, rng: &mut Xorshift<usize>) -> T;
/// Check whether the range is empty.
fn is_empty(&self) -> bool;
}
impl<T: SampleUniform + PartialOrd> SampleRange<T> for core::ops::Range<T> {
#[inline]
fn sample_single(self, rng: &mut Xorshift<usize>) -> T {
T::Sampler::sample_single(self.start, self.end, rng)
}
#[inline]
fn is_empty(&self) -> bool {
// !(self.start >= self.end)
self.start < self.end
}
}
impl<T: SampleUniform + PartialOrd> SampleRange<T> for core::ops::RangeInclusive<T> {
#[inline]
fn sample_single(self, rng: &mut Xorshift<usize>) -> T {
T::Sampler::sample_single_inclusive(self.start(), self.end(), rng)
}
#[inline]
fn is_empty(&self) -> bool {
// !(self.start() <= self.end())
self.start() > self.end()
}
}
pub trait WideningMultiply<RHS = Self> {
type Output;
fn wmul(self, x: RHS) -> Self::Output;
}
macro_rules! wmul_impl {
($ty:ty, $wide:ty, $shift:expr) => {
impl WideningMultiply for $ty {
type Output = ($ty, $ty);
#[inline(always)]
fn wmul(self, x: $ty) -> Self::Output {
let tmp = (self as $wide) * (x as $wide);
((tmp >> $shift) as $ty, tmp as $ty)
}
}
};
// simd bulk implementation
($(($ty:ident, $wide:ident),)+, $shift:expr) => {
$(
impl WideningMultiply for $ty {
type Output = ($ty, $ty);
#[inline(always)]
fn wmul(self, x: $ty) -> Self::Output {
// For supported vectors, this should compile to a couple
// supported multiply & swizzle instructions (no actual
// casting).
// TODO: optimize
let y: $wide = self.cast();
let x: $wide = x.cast();
let tmp = y * x;
let hi: $ty = (tmp >> $shift).cast();
let lo: $ty = tmp.cast();
(hi, lo)
}
}
)+
};
}
wmul_impl! { u8, u16, 8 }
wmul_impl! { u16, u32, 16 }
wmul_impl! { u32, u64, 32 }
wmul_impl! { u64, u128, 64 }
macro_rules! wmul_impl_large {
($ty:ty, $half:expr) => {
impl WideningMultiply for $ty {
type Output = ($ty, $ty);
#[inline(always)]
fn wmul(self, b: $ty) -> Self::Output {
const LOWER_MASK: $ty = !0 >> $half;
let mut low = (self & LOWER_MASK).wrapping_mul(b & LOWER_MASK);
let mut t = low >> $half;
low &= LOWER_MASK;
t += (self >> $half).wrapping_mul(b & LOWER_MASK);
low += (t & LOWER_MASK) << $half;
let mut high = t >> $half;
t = low >> $half;
low &= LOWER_MASK;
t += (b >> $half).wrapping_mul(self & LOWER_MASK);
low += (t & LOWER_MASK) << $half;
high += t >> $half;
high += (self >> $half).wrapping_mul(b >> $half);
(high, low)
}
}
};
// simd bulk implementation
(($($ty:ty,)+) $scalar:ty, $half:expr) => {
$(
impl WideningMultiply for $ty {
type Output = ($ty, $ty);
#[inline(always)]
fn wmul(self, b: $ty) -> Self::Output {
// needs wrapping multiplication
const LOWER_MASK: $scalar = !0 >> $half;
let mut low = (self & LOWER_MASK) * (b & LOWER_MASK);
let mut t = low >> $half;
low &= LOWER_MASK;
t += (self >> $half) * (b & LOWER_MASK);
low += (t & LOWER_MASK) << $half;
let mut high = t >> $half;
t = low >> $half;
low &= LOWER_MASK;
t += (b >> $half) * (self & LOWER_MASK);
low += (t & LOWER_MASK) << $half;
high += t >> $half;
high += (self >> $half) * (b >> $half);
(high, low)
}
}
)+
};
}
wmul_impl_large! { u128, 64 }
macro_rules! wmul_impl_usize {
($ty:ty) => {
impl WideningMultiply for usize {
type Output = (usize, usize);
#[inline(always)]
fn wmul(self, x: usize) -> Self::Output {
let (high, low) = (self as $ty).wmul(x as $ty);
(high as usize, low as usize)
}
}
};
}
#[cfg(target_pointer_width = "16")]
wmul_impl_usize! { u16 }
#[cfg(target_pointer_width = "32")]
wmul_impl_usize! { u32 }
#[cfg(target_pointer_width = "64")]
wmul_impl_usize! { u64 }
pub struct UniformInt<X> {
low: X,
range: X,
z: X,
}
macro_rules! uniform_int_impl {
($ty:ty, $unsigned:ident, $u_large:ident) => {
impl SampleUniform for $ty {
type Sampler = UniformInt<$ty>;
}
impl UniformSampler for UniformInt<$ty> {
type X = $ty;
#[inline]
fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized,
{
let low = *low_b.borrow();
let high = *high_b.borrow();
assert!(low < high, "Uniform::new called with `low >= high`");
UniformSampler::new_inclusive(low, high - 1)
}
#[inline]
fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized,
{
let low = *low_b.borrow();
let high = *high_b.borrow();
assert!(
low <= high,
"Uniform::new_inclusive called with `low > high`"
);
let unsigned_max = core::$u_large::MAX;
let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned;
let ints_to_reject = if range > 0 {
let range = $u_large::from(range);
(unsigned_max - range + 1) % range
} else {
0
};
UniformInt {
low,
range: range as $ty,
z: ints_to_reject as $unsigned as $ty,
}
}
#[inline]
fn sample(&self, rng: &mut Xorshift<$u_large>) -> Self::X {
let range = self.range as $unsigned as $u_large;
if range > 0 {
let unsigned_max = core::$u_large::MAX;
let zone = unsigned_max - (self.z as $unsigned as $u_large);
loop {
let v: $u_large = rng.gen();
let (hi, lo) = v.wmul(range);
if lo <= zone {
return self.low.wrapping_add(hi as $ty);
}
}
} else {
rng.gen()
}
}
#[inline]
fn sample_single<B1, B2>(
low_b: B1,
high_b: B2,
rng: &mut Xorshift<$u_large>,
) -> Self::X
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized,
{
let low = *low_b.borrow();
let high = *high_b.borrow();
assert!(low < high, "UniformSampler::sample_single: low >= high");
Self::sample_single_inclusive(low, high - 1, rng)
}
#[inline]
fn sample_single_inclusive<B1, B2>(
low_b: B1,
high_b: B2,
rng: &mut Xorshift<$u_large>,
) -> Self::X
where
B1: SampleBorrow<Self::X> + Sized,
B2: SampleBorrow<Self::X> + Sized,
{
let low = *low_b.borrow();
let high = *high_b.borrow();
assert!(
low <= high,
"UniformSampler::sample_single_inclusive: low > high"
);
let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned as $u_large;
if range == 0 {
return rng.gen();
}
let zone = if core::$unsigned::MAX <= core::u16::MAX as $unsigned {
let unsigned_max: $u_large = core::$u_large::MAX;
let ints_to_reject = (unsigned_max - range + 1) % range;
unsigned_max - ints_to_reject
} else {
(range << range.leading_zeros()).wrapping_sub(1)
};
loop {
let v: $u_large = rng.gen();
let (hi, lo) = v.wmul(range);
if lo <= zone {
return low.wrapping_add(hi as $ty);
}
}
}
}
};
}
uniform_int_impl! { usize, usize, usize }
pub struct Bernoulli {
p_int: u64,
}
const ALWAYS_TRUE: u64 = u64::max_value();
const SCALE: f64 = 2.0 * (1u64 << 63) as f64;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BernoulliError {
InvalidProbability,
}
impl Bernoulli {
#[inline]
pub fn new(p: f64) -> Result<Bernoulli, BernoulliError> {
if !(0.0..1.0).contains(&p) {
if p == 1.0 {
return Ok(Bernoulli { p_int: ALWAYS_TRUE });
}
return Err(BernoulliError::InvalidProbability);
}
Ok(Bernoulli {
p_int: (p * SCALE) as u64,
})
}
}
impl Distribution<bool, usize> for Bernoulli {
#[inline]
fn sample(&self, rng: &mut Xorshift<usize>) -> bool {
if self.p_int == ALWAYS_TRUE {
return true;
}
let v: u64 = rng.gen() as u64;
v < self.p_int
}
}
}