結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー ntk-ta01ntk-ta01
提出日時 2022-10-15 01:18:55
言語 Rust
(1.77.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,900 KB
testcase_01 AC 1 ms
4,904 KB
testcase_02 AC 1 ms
4,904 KB
testcase_03 AC 1 ms
4,904 KB
testcase_04 AC 1 ms
4,904 KB
testcase_05 AC 0 ms
4,904 KB
testcase_06 AC 1 ms
4,900 KB
testcase_07 AC 1 ms
6,948 KB
testcase_08 AC 1 ms
4,900 KB
testcase_09 AC 1 ms
6,948 KB
testcase_10 AC 1 ms
4,900 KB
testcase_11 AC 0 ms
6,948 KB
testcase_12 AC 1 ms
4,900 KB
testcase_13 AC 1 ms
4,904 KB
testcase_14 AC 1 ms
4,900 KB
testcase_15 AC 1 ms
4,904 KB
testcase_16 AC 1 ms
4,900 KB
testcase_17 AC 1 ms
4,908 KB
testcase_18 AC 1 ms
4,900 KB
testcase_19 AC 1 ms
4,900 KB
testcase_20 AC 1 ms
6,948 KB
testcase_21 AC 1 ms
6,952 KB
testcase_22 AC 0 ms
4,904 KB
testcase_23 AC 1 ms
6,952 KB
testcase_24 AC 1 ms
4,900 KB
testcase_25 AC 1 ms
6,948 KB
testcase_26 AC 1 ms
4,900 KB
testcase_27 AC 1 ms
6,948 KB
testcase_28 AC 1 ms
4,904 KB
testcase_29 AC 1 ms
4,900 KB
testcase_30 AC 1 ms
4,904 KB
testcase_31 AC 1 ms
4,904 KB
testcase_32 AC 1 ms
4,908 KB
testcase_33 AC 1 ms
6,948 KB
testcase_34 AC 1 ms
4,900 KB
testcase_35 AC 1 ms
4,904 KB
testcase_36 AC 0 ms
4,904 KB
testcase_37 AC 1 ms
4,900 KB
testcase_38 AC 1 ms
4,900 KB
testcase_39 AC 1 ms
4,900 KB
testcase_40 AC 1 ms
6,952 KB
testcase_41 AC 1 ms
4,900 KB
testcase_42 AC 1 ms
4,904 KB
testcase_43 AC 1 ms
4,908 KB
testcase_44 AC 1 ms
4,904 KB
testcase_45 AC 1 ms
4,900 KB
testcase_46 AC 1 ms
4,900 KB
testcase_47 AC 1 ms
4,900 KB
testcase_48 AC 1 ms
4,904 KB
testcase_49 AC 1 ms
6,948 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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

ソースコード

diff # 

// 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
        }
    }
}
0