QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636073 | #9451. Expected Waiting Time | ucup-team296# | AC ✓ | 823ms | 86728kb | Rust | 25.9kb | 2024-10-12 22:05:27 | 2024-10-12 22:05:28 |
Judging History
answer
//
pub mod solution {
//{"name":"b","group":"Manual","url":"","interactive":false,"timeLimit":2000,"tests":[{"input":"","output":""}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"b"}}}
#[allow(unused)]
use crate::dbg;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::math::modulo_runtime::ModRuntime;
use crate::algo_lib::misc::num_traits::HasConstants;
type Mod = ModRuntime;
pub fn gen_facts(n: usize, p: i32) -> Vec<Mod> {
let mut res = Vec::with_capacity(n);
res.push(Mod::new(1, p));
for x in 1..=n {
let num = Mod::new(x as i32, p);
res.push(*res.last().unwrap() * num);
}
res
}
pub struct CombinationsFact {
fact: Vec<Mod>,
fact_inv: Vec<Mod>,
invs: Vec<Mod>,
p: i32,
}
impl CombinationsFact {
#[allow(unused)]
pub fn new(n: usize, p: i32) -> Self {
let fact = gen_facts(n, p);
let mut fact_inv = fact.clone();
assert_eq!(fact_inv.len(), n + 1);
fact_inv[n] = Mod::new(1, p) / fact_inv[n];
for i in (1..n).rev() {
fact_inv[i] = fact_inv[i + 1] * Mod::new((i + 1) as i32, p);
}
let mut invs = fact_inv.clone();
for i in 1..=n {
invs[i] *= fact[i - 1];
}
Self {
fact,
fact_inv,
p,
invs,
}
}
pub fn fact(&self, n: usize) -> Mod {
self.fact[n]
}
fn c(&self, n: usize, k: usize) -> Mod {
if k > n {
return Mod::new(0, self.p);
}
self.fact[n] * self.fact_inv[k] * self.fact_inv[n - k]
}
}
fn solve(input: &mut Input, out: &mut Output, _test_case: usize) {
let tc = input.usize();
for _ in 0..tc {
let n = input.usize();
let p = input.i32();
let mut b = ModRuntime::new(input.i32(), p);
let A = ModRuntime::new(input.i32(), p);
let B = ModRuntime::new(input.i32(), p);
let mut a = vec![ModRuntime::new(0, p)];
for i in 1..=2 * n {
let a_last = *a.last().unwrap();
b = A * b + B;
a.push(a_last + ModRuntime::new(1, p) + b);
}
for i in 1..a.len() {
let prev = a[i - 1];
a[i] += prev;
}
let cnk = CombinationsFact::new(n * 2 + 2, p);
let mut brackets = vec![Mod::new(1, p); n + 1];
for i in 1..=n {
// TODO: slow?
brackets[i] = cnk.c(i * 2, i) * cnk.invs[i + 1];
}
let total_ways = brackets[n];
let mut res = Mod::new(0, p);
for k in 1..=n {
let ways = brackets[k - 1] * brackets[n - k];
let sz = k * 2;
let cnt = 2 * n - (sz - 1);
let sum_right = a[2 * n] - a[sz - 1];
let sum_left = a[cnt] - a[0];
let sum_dist = sum_right - sum_left;
res += ways * sum_dist;
}
res /= total_ways;
out.println(res);
}
}
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
solve(&mut input, &mut output, 1);
output.flush();
true
}
}
pub mod algo_lib {
pub mod collections {
pub mod last_exn {
use std::collections::BTreeSet;
pub trait LastExn<T> {
fn last_exn(&self) -> &T;
}
impl<T> LastExn<T> for &[T] {
fn last_exn(&self) -> &T {
self.last().unwrap()
}
}
impl<T> LastExn<T> for Vec<T> {
fn last_exn(&self) -> &T {
self.last().unwrap()
}
}
impl<T> LastExn<T> for BTreeSet<T> {
fn last_exn(&self) -> &T {
self.iter().next_back().unwrap()
}
}
}
}
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;
pub struct Input {
input: Box<dyn Read>,
buf: Vec<u8>,
at: usize,
buf_read: usize,
}
macro_rules! read_integer_fun {
($t:ident) => {
#[allow(unused)]
pub fn $t(&mut self) -> $t {
self.read_integer()
}
};
}
impl Input {
const DEFAULT_BUF_SIZE: usize = 4096;
///
/// Using with stdin:
/// ```no_run
/// use algo_lib::io::input::Input;
/// let stdin = std::io::stdin();
/// let input = Input::new(Box::new(stdin));
/// ```
///
/// For read files use ``new_file`` instead.
///
///
pub fn new(input: Box<dyn Read>) -> Self {
Self {
input,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
}
}
pub fn new_stdin() -> Self {
let stdin = std::io::stdin();
Self::new(Box::new(stdin))
}
pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new(Box::new(file))
}
pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
Self {
input,
buf: vec![0; buf_size],
at: 0,
buf_read: 0,
}
}
pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new_with_size(Box::new(file), buf_size)
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
Some(self.buf[self.at])
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !char::from(b).is_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if char::from(c).is_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() {
None
} else {
Some(res)
}
}
//noinspection RsSelfConvention
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn has_more_elements(&mut self) -> bool {
!self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.read());
}
res
}
pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.string());
}
res
}
pub fn read_line(&mut self) -> String {
let mut res = String::new();
while let Some(c) = self.get() {
if c == b'\n' {
break;
}
if c == b'\r' {
if self.peek() == Some(b'\n') {
self.get();
}
break;
}
res.push(c.into());
}
res
}
#[allow(clippy::should_implement_trait)]
pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
InputIterator {
input: self,
phantom: Default::default(),
}
}
fn read_integer<T: FromStr + Debug>(&mut self) -> T
where
<T as FromStr>::Err: Debug,
{
let res = self.read_string();
res.parse::<T>().unwrap()
}
fn read_string(&mut self) -> String {
match self.next_token() {
None => {
panic!("Input exhausted");
}
Some(res) => unsafe { String::from_utf8_unchecked(res) },
}
}
pub fn string_as_string(&mut self) -> String {
self.read_string()
}
pub fn string(&mut self) -> Vec<u8> {
self.read_string().into_bytes()
}
fn read_char(&mut self) -> char {
self.skip_whitespace();
self.get().unwrap().into()
}
fn read_float(&mut self) -> f64 {
self.read_string().parse().unwrap()
}
pub fn f64(&mut self) -> f64 {
self.read_float()
}
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
read_integer_fun!(i32);
read_integer_fun!(i64);
read_integer_fun!(i128);
read_integer_fun!(u32);
read_integer_fun!(u64);
read_integer_fun!(usize);
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for String {
fn read(input: &mut Input) -> Self {
input.read_string()
}
}
impl Readable for char {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl Readable for f64 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl Readable for f32 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.vec(size)
}
}
pub struct InputIterator<T: Readable> {
input: Input,
phantom: PhantomData<T>,
}
impl<T: Readable> Iterator for InputIterator<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.input.skip_whitespace();
self.input.peek().map(|_| self.input.read())
}
}
macro_rules! read_integer {
($t:ident) => {
impl Readable for $t {
fn read(input: &mut Input) -> Self {
input.read_integer()
}
}
};
}
read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;
pub struct Output {
output: Box<dyn Write>,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
}
impl Output {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: false,
}
}
pub fn new_stdout() -> Self {
let stdout = std::io::stdout();
Self::new(Box::new(stdout))
}
pub fn new_file(path: impl AsRef<std::path::Path>) -> Self {
let file = std::fs::File::create(path).unwrap();
Self::new(Box::new(file))
}
pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: true,
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.at = 0;
self.output.flush().expect("Couldn't flush output");
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
}
pub fn println<T: Writable>(&mut self, s: T) {
s.write(self);
self.put(b'\n');
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
for i in arg {
i.write(self);
self.put(b'\n');
}
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
}
impl Write for Output {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
if self.auto_flush {
self.flush();
}
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter_ref(self.iter());
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self[..].write(output);
}
}
macro_rules! write_to_string {
($t:ident) => {
impl Writable for $t {
fn write(&self, output: &mut Output) {
self.to_string().write(output);
}
}
};
}
write_to_string!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);
impl<T: Writable, U: Writable> Writable for (T, U) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
}
}
impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
output.put(b' ');
self.2.write(output);
}
}
}
}
pub mod math {
pub mod modulo_runtime {
use crate::algo_lib::collections::last_exn::LastExn;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::io::output::Writable;
use crate::algo_lib::misc::num_traits::ConvSimple;
use crate::algo_lib::misc::num_traits::HasConstants;
use std::io::Write;
#[derive(Copy, Clone, Eq, PartialEq, Default, Ord, PartialOrd)]
pub struct ModRuntime {
value: i32,
m: i32,
}
impl ModRuntime {
fn assert_reasonable_pair(a: &Self, b: &Self) {
assert_ne!(a.m, 0);
assert_ne!(a.m, 0);
assert_eq!(a.m, b.m);
}
fn rev_rec(a: i32, m: i32) -> i32 {
if a == 1 {
return a;
}
((1 - Self::rev_rec(m % a, a) as i64 * m as i64) / a as i64 + m as i64) as i32
}
#[allow(dead_code)]
pub fn inv(self) -> Self {
Self {
value: Self::rev_rec(self.value, self.m),
m: self.m,
}
}
#[allow(dead_code)]
#[inline]
pub fn new(mut x: i32, m: i32) -> Self {
if x < 0 {
x += m;
if x < 0 {
x %= m;
x += m;
}
} else if x >= m {
x -= m;
if x >= m {
x %= m;
}
}
assert!(0 <= x && x < m);
Self { value: x, m }
}
pub fn pown(self, pw: usize) -> Self {
if pw == 0 {
Self::new(1, self.m)
} else if pw == 1 {
self
} else {
let half = self.pown(pw / 2);
let res = half * half;
if pw % 2 == 0 {
res
} else {
res * self
}
}
}
// TODO: `pw` should be [T], which implements "integer"
pub fn pow_i128(self, pw: i128) -> Self {
if pw == 0 {
Self::new(1, self.m)
} else if pw == 1 {
self
} else {
let half = self.pow_i128(pw / 2);
let res = half * half;
if pw % 2 == 0 {
res
} else {
res * self
}
}
}
pub fn gen_powers(base: Self, n: usize) -> Vec<Self> {
let mut res = Vec::with_capacity(n);
res.push(Self::ONE);
for _ in 1..n {
res.push(*res.last_exn() * base);
}
res
}
pub fn value(&self) -> i32 {
self.value
}
}
impl std::fmt::Display for ModRuntime {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.value)
}
}
impl std::fmt::Debug for ModRuntime {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
const MAX: usize = 100;
if self.value <= MAX as i32 {
write!(f, "{}", self.value)
} else if self.value >= self.m - MAX as i32 {
write!(f, "-{}", self.m - self.value)
} else {
// TODO: not all ..MAX has inverse
// for denum in 1..MAX {
// for num in 1..MAX {
// if Self::new(num as i32, self.m) / Self::new(denum as i32, self.m) == *self {
// return write!(f, "{}/{}", num, denum);
// }
// }
// }
write!(f, "(?? {} ??)", self.value)
}
}
}
impl std::ops::Add for ModRuntime {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self::assert_reasonable_pair(&self, &rhs);
let res = self.value as i64 + rhs.value as i64;
if res >= self.m as i64 {
ModRuntime::new((res - self.m as i64) as i32, self.m)
} else {
ModRuntime::new(res as i32, self.m)
}
}
}
impl std::ops::AddAssign for ModRuntime {
fn add_assign(&mut self, rhs: Self) {
Self::assert_reasonable_pair(self, &rhs);
let z = *self + rhs;
self.value = z.value;
}
}
impl std::ops::Sub for ModRuntime {
type Output = Self;
fn sub(self, rhs: Self) -> Self::Output {
Self::assert_reasonable_pair(&self, &rhs);
let res = self.value - rhs.value;
if res < 0 {
ModRuntime::new(res + self.m, self.m)
} else {
ModRuntime::new(res, self.m)
}
}
}
impl std::ops::SubAssign for ModRuntime {
fn sub_assign(&mut self, rhs: Self) {
Self::assert_reasonable_pair(self, &rhs);
self.value -= rhs.value;
if self.value < 0 {
self.value += self.m;
}
}
}
impl std::ops::Mul for ModRuntime {
type Output = Self;
fn mul(self, rhs: Self) -> Self::Output {
Self::assert_reasonable_pair(&self, &rhs);
let res = (self.value as i64) * (rhs.value as i64) % (self.m as i64);
ModRuntime::new(res as i32, self.m)
}
}
impl std::ops::MulAssign for ModRuntime {
fn mul_assign(&mut self, rhs: Self) {
Self::assert_reasonable_pair(self, &rhs);
self.value = ((self.value as i64) * (rhs.value as i64) % (self.m as i64)) as i32;
}
}
impl std::ops::Div for ModRuntime {
type Output = Self;
#[allow(clippy::suspicious_arithmetic_impl)]
fn div(self, rhs: Self) -> Self::Output {
Self::assert_reasonable_pair(&self, &rhs);
let rhs_inv = rhs.inv();
self * rhs_inv
}
}
impl std::ops::DivAssign for ModRuntime {
#[allow(clippy::suspicious_op_assign_impl)]
fn div_assign(&mut self, rhs: Self) {
Self::assert_reasonable_pair(self, &rhs);
*self *= rhs.inv();
}
}
impl std::ops::Neg for ModRuntime {
type Output = Self;
fn neg(self) -> Self::Output {
Self::assert_reasonable_pair(&self, &self);
Self::new(self.m - self.value, self.m)
}
}
impl Writable for ModRuntime {
fn write(&self, output: &mut Output) {
output.write_fmt(format_args!("{}", self.value)).unwrap();
}
}
impl HasConstants<ModRuntime> for ModRuntime {
// This doesn't make much sense, but hope we never use
const MAX: ModRuntime = unreachable!();
const MIN: ModRuntime = unreachable!();
const ZERO: ModRuntime = unreachable!();
const ONE: ModRuntime = ModRuntime { value: 0, m: 0 };
const TWO: ModRuntime = unreachable!();
}
impl ConvSimple<ModRuntime> for ModRuntime {
fn from_i32(_val: i32) -> ModRuntime {
unreachable!()
}
fn to_i32(self) -> i32 {
self.value
}
fn to_f64(self) -> f64 {
self.value as f64
}
}
pub struct RuntimeModBuilder {
modulo: i32,
}
impl RuntimeModBuilder {
pub fn new_builder(modulo: i32) -> Self {
Self { modulo }
}
#[allow(clippy::new_ret_no_self)]
pub fn new(&self, x: i32) -> ModRuntime {
ModRuntime {
value: x,
m: self.modulo,
}
}
}
}
}
pub mod misc {
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
($first_val:expr, $($val:expr),+ $(,)?) => {
eprint!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val);
($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
eprintln!();
};
($first_val:expr) => {
eprintln!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val)
};
}
}
pub mod num_traits {
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Sub;
use std::ops::SubAssign;
pub trait HasConstants<T> {
const MAX: T;
const MIN: T;
const ZERO: T;
const ONE: T;
const TWO: T;
}
pub trait ConvSimple<T> {
fn from_i32(val: i32) -> T;
fn to_i32(self) -> i32;
fn to_f64(self) -> f64;
}
pub trait Signum {
fn signum(&self) -> i32;
}
pub trait Number:
Copy
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ PartialOrd
+ PartialEq
+ HasConstants<Self>
+ Default
+ Debug
+ Sized
+ ConvSimple<Self>
{
}
impl<
T: Copy
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ PartialOrd
+ PartialEq
+ HasConstants<Self>
+ Default
+ Debug
+ Sized
+ ConvSimple<Self>,
> Number for T
{
}
macro_rules! has_constants_impl {
($t: ident) => {
impl HasConstants<$t> for $t {
// TODO: remove `std` for new rust version..
const MAX: $t = std::$t::MAX;
const MIN: $t = std::$t::MIN;
const ZERO: $t = 0;
const ONE: $t = 1;
const TWO: $t = 2;
}
impl ConvSimple<$t> for $t {
fn from_i32(val: i32) -> $t {
val as $t
}
fn to_i32(self) -> i32 {
self as i32
}
fn to_f64(self) -> f64 {
self as f64
}
}
};
}
has_constants_impl!(i32);
has_constants_impl!(i64);
has_constants_impl!(i128);
has_constants_impl!(u32);
has_constants_impl!(u64);
has_constants_impl!(u128);
has_constants_impl!(usize);
has_constants_impl!(u8);
impl ConvSimple<Self> for f64 {
fn from_i32(val: i32) -> Self {
val as f64
}
fn to_i32(self) -> i32 {
self as i32
}
fn to_f64(self) -> f64 {
self
}
}
impl HasConstants<Self> for f64 {
const MAX: Self = Self::MAX;
const MIN: Self = -Self::MAX;
const ZERO: Self = 0.0;
const ONE: Self = 1.0;
const TWO: Self = 2.0;
}
impl<T: Number + Ord> Signum for T {
fn signum(&self) -> i32 {
match self.cmp(&T::ZERO) {
Ordering::Greater => 1,
Ordering::Less => -1,
Ordering::Equal => 0,
}
}
}
}
}
}
fn main() {
let input = algo_lib::io::input::Input::new_stdin();
let mut output = algo_lib::io::output::Output::new_stdout();
crate::solution::run(input, output);
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2284kb
input:
5 1 1000000007 0 1 0 2 1000000007 0 1 1 2 7 5 2 3 3 31 15 6 24 20 1000000007 0 1 0
output:
1 12 1 21 879705565
result:
ok 5 number(s): "1 12 1 21 879705565"
Test #2:
score: 0
Accepted
time: 764ms
memory: 2688kb
input:
4400 3954 1000000007 0 1 0 1306 1000000007 0 1 0 3774 1000000007 0 1 0 3345 1000000007 0 1 0 891 1000000007 0 1 0 2462 1000000007 0 1 0 237 1000000007 0 1 0 26 1000000007 0 1 0 2510 1000000007 0 1 0 637 1000000007 0 1 0 3250 1000000007 0 1 0 3447 1000000007 0 1 0 1222 1000000007 0 1 0 133 1000000007...
output:
440618338 378292891 979368645 915766295 343598158 80867595 161627927 517387931 396936703 42785642 945720545 764273281 186237656 635777911 164064906 548455037 991964184 468137124 561243246 118562285 856945294 642467240 23673926 808943705 897417615 462422554 656411244 204288121 997894281 244685651 762...
result:
ok 4400 numbers
Test #3:
score: 0
Accepted
time: 809ms
memory: 86728kb
input:
1019 338 1863833207 1820742817 1507924477 1822273457 770 1386304741 1088481071 1216187083 170973217 597 1604266739 620750027 196415899 456280997 105 1008587891 184044403 24836083 926135599 357 1165127407 440925347 1103369747 912263123 82 1639766993 263045351 631010551 1412721139 928 1715915153 25383...
output:
1532578211 839037587 1047387343 827110887 825754860 1399761197 267796211 1563605211 1628148612 510782452 1009499206 977929696 466163317 246777775 1781337180 700999207 522771237 42312781 172374583 319038379 563256698 1400403161 22552986 1408276343 558752169 1050819260 174447415 844160548 1382940913 1...
result:
ok 1019 numbers
Test #4:
score: 0
Accepted
time: 801ms
memory: 10648kb
input:
217 31752 1623636743 381890923 885513569 842557939 44560 1671300349 1133398261 1076377361 138151151 98395 1887613031 1552853849 1167776639 1748368931 38388 1221893927 524645339 598717199 864504559 46484 1161165839 833729009 348202331 407607601 14134 1500136753 247946861 1029519499 420912461 42361 12...
output:
921943129 1651287678 1204818336 685557670 348324702 1348834532 684106754 1802861733 294146103 1181847835 393402724 771264676 1357541910 336262290 1519052686 965265375 164416232 536332209 664177339 279762508 172270575 296113856 676553568 56580590 1662307723 551032870 849878353 899756098 1043540760 65...
result:
ok 217 numbers
Test #5:
score: 0
Accepted
time: 823ms
memory: 10772kb
input:
209 29771 1072350767 215063557 929759989 884416571 55201 1330151437 375869047 1089916759 1006803043 44446 1255569503 974485139 1100573447 468049237 38112 1088575729 690554509 139043089 318478729 59665 1197676111 958924997 1062562733 504417349 26297 1267535141 800679281 972314209 417253079 19848 1470...
output:
1019773842 530587777 960231793 799694163 777561611 5502176 357632543 758954057 966358573 1023410809 949841520 1495179331 1580320049 173875471 2220116 469298866 1337750009 369625733 747522220 143937247 1286370836 135996013 210044979 1583248565 657653951 1035620126 160616212 193166047 147168296 194451...
result:
ok 209 numbers
Test #6:
score: 0
Accepted
time: 807ms
memory: 10884kb
input:
191 4581 1215490597 542057431 695641117 341312327 76198 1830024701 1063458349 588883499 1260572737 76694 1445111947 1069466003 941483509 268919069 92431 1384691513 15731591 390776461 943271249 63234 1097808793 204272807 857954509 763222181 26427 1746295877 743699191 1671886939 1655403307 91012 19997...
output:
660812054 1707568418 155249600 645552623 671226426 50129037 971925203 1638809868 463571080 143058581 403506184 767222482 666935871 1092771100 416048275 1536775747 475955650 73199758 578511368 51576569 1380151783 515363742 1021989523 892069331 1088408017 1337534689 715624643 1241212077 730954505 1286...
result:
ok 191 numbers
Extra Test:
score: 0
Extra Test Passed