結果
| 問題 | No.381 名声値を稼ごう Extra |
| ユーザー |
 Keigo Oka
|
| 提出日時 | 2019-04-19 19:55:28 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 27,788 bytes |
| コンパイル時間 | 17,951 ms |
| コンパイル使用メモリ | 390,104 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-09-22 13:46:27 |
| 合計ジャッジ時間 | 14,140 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
ソースコード
#![allow(non_snake_case, unused_imports)]
//////////////////////////////// LIBRARY START ////////////////////////////////
#[macro_use]
pub mod contest {
#[macro_use]
pub mod num {
pub use self::biguint::*;
pub use self::num::*;
#[macro_use]
pub mod num {
use std::cmp::PartialEq;
use std::ops::*;
pub trait NumOps<Rhs = Self, Output = Self>:
Add<Rhs, Output = Output>
+ Sub<Rhs, Output = Output>
+ Mul<Rhs, Output = Output>
+ Div<Rhs, Output = Output>
+ Rem<Rhs, Output = Output>
{
}
pub trait RefNum<Base>: NumOps<Base, Base> + for<'r> NumOps<&'r Base, Base> {}
pub trait Num: Zero + One + RefNum<Self> + PartialEq<Self>
where
Self: Sized,
{
}
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
macro_rules! impl_num {
( $t: ty, $zero: expr, $one: expr) => {
impl Zero for $t {
fn zero() -> $t {
$zero
}
}
impl One for $t {
fn one() -> $t {
$one
}
}
impl NumOps<$t, $t> for $t {}
impl<'r> NumOps<&'r $t, $t> for $t {}
impl RefNum<$t> for $t {}
impl Num for $t {}
};
}
impl_num!(i32, 0, 1);
impl_num!(i64, 0, 1);
impl_num!(f32, 0.0, 1.0);
impl_num!(f64, 0.0, 1.0);
#[cfg(test)]
mod test {
macro_rules! assert_op {
($left:ident $op:tt $right:ident == $expected:expr) => {
assert_eq!((&$left) $op (&$right), $expected);
assert_eq!((&$left) $op $right.clone(), $expected);
assert_eq!($left.clone() $op (&$right), $expected);
assert_eq!($left.clone() $op $right.clone(), $expected);
};
}
#[test]
fn test_it() {
let a = 3;
let b = 2;
assert_op!(a * b == 6);
assert_op!(a + b == 5);
}
}
}
#[macro_use]
pub mod algorithm {
pub fn add3(a: u32, b: u32, carry: bool) -> (u32, bool) {
let (x, c) = a.overflowing_add(b);
if !carry {
return (x, c);
}
let (x2, c2) = x.overflowing_add(1);
(x2, c || c2)
}
pub fn sub3(a: u32, b: u32, carry: bool) -> (u32, bool) {
let (x, c) = a.overflowing_sub(b);
if !carry {
return (x, c);
}
let (x2, c2) = x.overflowing_sub(1);
(x2, c || c2)
}
}
#[macro_use]
pub mod biguint {
use std;
use std::cmp::Ordering;
use std::ops::*;
use super::algorithm;
use super::{One, Zero};
#[derive(Clone, Debug, Hash)]
pub struct BigUint {
// [3, 2] represents 3 + (2 << 32).
data: Vec<u32>,
}
impl std::fmt::Display for BigUint {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
if self.data.len() == 0 {
return write!(f, "0");
}
let base = 1_000_000_000u64;
// [3, 2] represents 3 + (2 * base).
let mut res = vec![];
for d in self.data.iter().rev() {
let mut carry = *d as u64;
for x in res.iter_mut() {
let v = (*x << 32) + carry;
*x = v % base;
carry = v / base;
}
while carry > 0 {
res.push(carry % base);
carry /= base;
}
}
debug_assert_ne!(res.last(), Some(&0));
let (rest, top) = res.split_at(res.len() - 1);
write!(f, "{}", top[0])?;
for x in rest.iter().rev() {
write!(f, "{:09}", x)?;
}
Ok(())
}
}
impl PartialEq for BigUint {
#[inline]
fn eq(&self, other: &BigUint) -> bool {
match self.cmp(other) {
Ordering::Equal => true,
_ => false,
}
}
}
impl Eq for BigUint {}
impl PartialOrd for BigUint {
#[inline]
fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for BigUint {
#[inline]
fn cmp(&self, other: &BigUint) -> Ordering {
cmp_slice(&self.data[..], &other.data[..])
}
}
fn cmp_slice(a: &[u32], b: &[u32]) -> Ordering {
debug_assert!(a.last() != Some(&0));
debug_assert!(b.last() != Some(&0));
if a.len() < b.len() {
return Ordering::Less;
} else if a.len() > b.len() {
return Ordering::Greater;
}
for i in (0..a.len()).rev() {
let c = a[i].cmp(&b[i]);
if c != Ordering::Equal {
return c;
}
}
Ordering::Equal
}
impl From<u64> for BigUint {
fn from(mut x: u64) -> BigUint {
let mut data = vec![];
while x > 0 {
data.push((x & u32::max_value() as u64) as u32);
x >>= 32;
}
BigUint { data: data }
}
}
#[derive(Debug, PartialEq)]
pub struct ParseBigUintError;
impl std::str::FromStr for BigUint {
type Err = ParseBigUintError;
fn from_str(s: &str) -> Result<BigUint, ParseBigUintError> {
let s = s.as_bytes();
if s.iter().any(|c| *c < b'0' || b'9' < *c) {
return Err(ParseBigUintError);
}
fn parse_u32(s: &[u8]) -> u32 {
s.iter().fold(0u32, |acc, c| acc * 10 + (*c - b'0') as u32)
}
let mut data = vec![];
let base = 1_000_000_000u64;
let chunk_size = 9;
let (head, tail) = s.split_at(s.len() % chunk_size);
if !head.is_empty() {
data.push(parse_u32(head));
}
debug_assert_eq!(tail.len() % chunk_size, 0);
for ch in tail.chunks(chunk_size) {
// data *= base
let mut carry = parse_u32(ch) as u64;
for d in data.iter_mut() {
let v = *d as u64 * base + carry;
*d = v as u32;
carry = v >> 32;
}
if carry > 0 {
data.push(carry as u32);
}
}
// For "0" etc.
while data.last() == Some(&0) {
data.pop();
}
debug_assert_ne!(data.last(), Some(&0));
Ok(BigUint { data: data })
}
}
impl Zero for BigUint {
fn zero() -> BigUint {
BigUint::from(0)
}
}
impl One for BigUint {
fn one() -> BigUint {
BigUint::from(1)
}
}
impl<'a, 'b> Add<&'b BigUint> for &'a BigUint {
type Output = BigUint;
fn add(self, other: &'b BigUint) -> BigUint {
let n = std::cmp::max(self.data.len(), other.data.len());
let mut data = vec![];
let mut carry = false;
for i in 0..n {
let a = self.data.get(i).map_or(0, |x| *x);
let b = other.data.get(i).map_or(0, |x| *x);
let (x, c) = algorithm::add3(a, b, carry);
carry = c;
data.push(x);
}
if carry {
data.push(1);
}
debug_assert_ne!(data.last(), Some(&0));
BigUint { data: data }
}
}
impl<'a, 'b> Sub<&'b BigUint> for &'a BigUint {
type Output = BigUint;
fn sub(self, other: &'b BigUint) -> BigUint {
debug_assert!(self >= other);
let n = std::cmp::max(self.data.len(), other.data.len());
let mut data = vec![];
let mut carry = false;
for i in 0..n {
let a = self.data.get(i).map_or(0, |x| *x);
let b = other.data.get(i).map_or(0, |x| *x);
let (x, c) = algorithm::sub3(a, b, carry);
carry = c;
data.push(x);
}
debug_assert!(!carry);
while data.last() == Some(&0) {
data.pop();
}
debug_assert_ne!(data.last(), Some(&0));
BigUint { data: data }
}
}
impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint {
type Output = BigUint;
fn mul(self, other: &'b BigUint) -> BigUint {
if self == &BigUint::zero() || other == &BigUint::zero() {
return BigUint::zero();
}
let n = self.data.len() + other.data.len() - 1;
let mut data = vec![];
let mut carry = 0u64;
let u32max = u32::max_value() as u64;
for i in 0..n {
// 2 1 0 - self (j)
// 1 0 - other(k)
// ----------------
// 2,0 1,0 0,0
// 2,1 1,1 0,1
// | | | |
// 3 2 1 0 - i
let mut digit = carry & u32max;
carry >>= 32;
let from = if i + 1 >= other.data.len() {
i + 1 - other.data.len()
} else {
0
};
for j in from..std::cmp::min(i + 1, self.data.len()) {
let k = i - j;
let x = self.data[j] as u64;
let y = other.data[k] as u64;
let val = digit + x * y;
digit = val & u32max;
carry += val >> 32;
}
debug_assert!(digit <= u32max);
data.push(digit as u32);
}
if carry > 0 {
debug_assert!(carry <= u32max);
data.push(carry as u32);
}
debug_assert_ne!(data.last(), Some(&0));
BigUint { data: data }
}
}
macro_rules! impl_others {
($tr:tt $func: ident) => {
impl<'a> $tr<BigUint> for &'a BigUint {
type Output = BigUint;
fn $func(self, x: BigUint) -> BigUint {
self.$func(&x)
}
}
impl<'b> $tr<&'b BigUint> for BigUint {
type Output = BigUint;
fn $func(self, x: &'b BigUint) -> BigUint {
(&self).$func(x)
}
}
impl $tr<BigUint> for BigUint {
type Output = BigUint;
fn $func(self, x: BigUint) -> BigUint {
(&self).$func(&x)
}
}
};
}
impl_others!(Add add);
impl_others!(Sub sub);
impl_others!(Mul mul);
#[cfg(test)]
mod test {
use super::*;
macro_rules! assert_op {
($left:ident $op:tt $right:ident == $expected:expr) => {
assert_eq!((&$left) $op (&$right), $expected);
assert_eq!((&$left) $op $right.clone(), $expected);
assert_eq!($left.clone() $op (&$right), $expected);
assert_eq!($left.clone() $op $right.clone(), $expected);
};
}
#[test]
fn test_add() {
let a = BigUint::from(3);
let b = BigUint::from(2);
let c = BigUint::from(5);
assert_op!(a + b == c);
}
#[test]
fn test_add_zero() {
let a = BigUint::zero();
let b = BigUint::one();
assert_op!(a + a == a);
assert_op!(a + b == b);
assert_op!(b + a == b);
}
#[test]
fn test_add_big() {
let a = BigUint::from(3_000_000_000_000);
let b = BigUint::from(2_000_000_000_000);
let c = BigUint::from(5_000_000_000_000);
assert_op!(a + b == c);
}
#[test]
fn test_add_with_carry() {
use std;
let a = BigUint::from(std::u32::MAX as u64);
let b = BigUint::from(1);
let c = BigUint::from(std::u32::MAX as u64 + 1);
assert_op!(a + b == c);
}
#[test]
fn test_sub() {
let a = BigUint::from(3);
let b = BigUint::from(2);
let c = BigUint::from(5);
assert_op!(c - b == a);
}
#[test]
fn test_sub_zero() {
let a = BigUint::zero();
let b = BigUint::one();
assert_op!(b - a == b);
assert_op!(a - a == a);
}
#[test]
fn test_sub_big() {
let a = BigUint::from(3_000_000_000_000);
let b = BigUint::from(2_000_000_000_000);
let c = BigUint::from(5_000_000_000_000);
assert_op!(c - b == a);
}
#[test]
fn test_sub_with_carry() {
use std;
let a = BigUint::from(std::u32::MAX as u64);
let b = BigUint::from(1);
let c = BigUint::from(std::u32::MAX as u64 + 1);
assert_op!(c - b == a);
}
#[test]
fn test_mul() {
let a = BigUint::from(3);
let b = BigUint::from(2);
let c = BigUint::from(6);
assert_op!(a * b == c);
}
#[test]
fn test_mul_zero() {
let a = BigUint::zero();
let b = BigUint::one();
assert_op!(a * b == a);
assert_op!(a * a == a);
}
#[test]
fn test_mul_big() {
let a = BigUint::from(3_000_000_000_000);
let b = BigUint::from(2_000_000_000_000);
let c = BigUint::from(6_000_000_000_000);
let d = BigUint::from(1_000_000_000_000);
let e = &d * &c;
assert_op!(a * b == e);
}
#[test]
fn test_mul_with_carry() {
let a = BigUint::from(2);
let b = BigUint::from(1u64 << 31);
let c = BigUint::from(1u64 << 32);
assert_op!(a * b == c);
}
#[test]
fn test_cmp() {
let a = BigUint::from(3);
let b = BigUint::from(2);
let c = BigUint::zero();
assert!(a > b);
assert!(b < a);
assert!(a == a);
assert!(c == c);
assert!(a > c);
assert!(c < a);
}
#[test]
fn test_big_cmp() {
let a = BigUint::from(3_000_000_000_000u64);
let b = BigUint::from(2_000_000_000_000u64);
let c = BigUint::from(2_000_000_000_001u64);
assert!(a == a);
assert!(a > b);
assert!(b < a);
assert!(c > b);
assert!(b < c);
}
macro_rules! assert_from_str {
($a: expr, $b: expr) => {{
let a = BigUint::from_str($a).unwrap();
let b = BigUint::from($b);
assert_eq!(a, b);
}};
}
#[test]
fn test_from_str() {
use std::str::FromStr;
assert_from_str!("0", 0);
assert_from_str!("123", 123);
assert_from_str!("1000000000", 1000000000);
assert_from_str!("10000000000", 10000000000);
assert_from_str!("12345678901", 12345678901);
}
#[test]
fn test_from_str_big() {
use std::str::FromStr;
let base = BigUint::from(1000000000);
let a = &base * &base * &base;
assert_eq!(BigUint::from_str("1000000000000000000000000000"), Ok(a));
}
#[test]
fn test_fmt() {
use std::str::FromStr;
assert_eq!("0".to_string(), format!("{}", BigUint::from(0)));
assert_eq!("1".to_string(), format!("{}", BigUint::from(1)));
assert_eq!(
"123456789".to_string(),
format!("{}", BigUint::from(123456789))
);
assert_eq!(
"1000000001".to_string(),
format!("{}", BigUint::from(1000000001))
);
assert_eq!(
"12345678901".to_string(),
format!("{}", BigUint::from(12345678901))
);
assert_eq!(
"123456789012345678901234567890".to_string(),
format!(
"{}",
BigUint::from_str("123456789012345678901234567890").unwrap()
)
);
}
}
}
}
#[macro_use]
pub mod prelude {
pub use self::myvec::*;
#[macro_use]
pub mod primitive {
pub trait ToUsize: Sized {
fn to_usize(self) -> usize;
}
impl ToUsize for i32 {
#[inline]
fn to_usize(self) -> usize {
self as usize
}
}
impl ToUsize for i64 {
#[inline]
fn to_usize(self) -> usize {
self as usize
}
}
impl ToUsize for usize {
#[inline]
fn to_usize(self) -> usize {
self
}
}
}
#[macro_use]
pub mod myvec {
use std::fmt;
use std::iter::FromIterator;
use std::ops::*;
pub use super::primitive::ToUsize;
/// `Vec` indexable with `i32`, `i64` or `usize`.
#[derive(Clone, Debug, PartialEq, PartialOrd)]
pub struct MyVec<T>(pub Vec<T>);
/// Creates `MyVec`
#[macro_export]
macro_rules! v {
( $( $x:expr ),* ) => {
MyVec(vec![ $( $x, )* ])
};
( $x:expr ; $n:expr ) => {
{
MyVec(vec![$x; $n as usize])
}
};
}
impl<T: fmt::Display> fmt::Display for MyVec<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let n = self.len();
for i in 0..n {
let r = if i < n - 1 {
writeln!(f, "{}", self.0[i])
} else {
write!(f, "{}", self.0[i])
};
if r.is_err() {
return r;
}
}
Ok(())
}
}
impl<T> Deref for MyVec<T> {
type Target = Vec<T>;
#[inline]
fn deref(&self) -> &Vec<T> {
&self.0
}
}
impl<T> DerefMut for MyVec<T> {
#[inline]
fn deref_mut(&mut self) -> &mut Vec<T> {
&mut self.0
}
}
impl<T> FromIterator<T> for MyVec<T> {
#[inline]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
MyVec(Vec::from_iter(iter))
}
}
impl<T, I: ToUsize> Index<I> for MyVec<T> {
type Output = T;
#[inline]
fn index(&self, i: I) -> &T {
&self.0[i.to_usize()]
}
}
impl<T, I: ToUsize> IndexMut<I> for MyVec<T> {
#[inline]
fn index_mut(&mut self, i: I) -> &mut T {
&mut self.0[i.to_usize()]
}
}
#[test]
fn test_myvec() {
let mut x = v![3, 2, 1];
x.sort();
assert_eq!(vec![1, 2, 3], *x);
let i = 1i32;
assert_eq!(2, x[i]);
x[i] = 3;
assert_eq!(3, x[i]);
let u = 1usize;
assert_eq!(3, x[u]);
x[u] = 2;
assert_eq!(2, x[u]);
assert_eq!(2, x[1]);
assert_eq!("MyVec([1, 2, 3])", format!("{:?}", x));
assert_eq!(v![1, 2, 3], x);
assert_eq!("1\n2\n3", format!("{}", x));
let mut y = v![v![1, 2]; 3];
y[0][0] = 2;
assert_eq!(vec![2, 2], *y[0]);
assert_eq!(vec![1, 2], *y[1]);
}
}
}
#[macro_use]
pub mod io {
/// Scanner
///
/// # Example
/// ```
/// use contest::io::Scanner;
/// let mut sc = Scanner::new("1 2 \n\n \r\t \n 3".as_bytes());
/// assert_eq!("1".to_string(), sc.next::<String>());
/// let v = sc.nexts(2);
/// assert_eq!(2i32, v[0]);
/// assert_eq!(3i32, v[1]);
///
/// // To create a scanner from stdin:
/// Scanner::new(std::io::stdin());
/// ```
use std;
use std::io;
use std::io::BufRead;
use super::prelude::MyVec;
pub struct Scanner<R: io::Read> {
br: io::BufReader<R>,
// Read tokens are stored in reversed order per line.
buf: Vec<String>,
}
pub fn new<R: io::Read>(r: R) -> Scanner<R> {
Scanner::new(r)
}
impl<R: io::Read> Scanner<R> {
#[inline]
pub fn new(r: R) -> Scanner<R> {
Scanner {
br: io::BufReader::new(r),
buf: vec![],
}
}
#[inline]
pub fn next<T>(&mut self) -> T
where
T: std::str::FromStr,
T::Err: std::fmt::Debug,
{
self.next_string()
.map(|s| s.parse::<T>().expect("Parse failed: "))
.expect("Unexpected EOF")
}
#[inline]
pub fn nexts<T>(&mut self, n: i32) -> MyVec<T>
where
T: std::str::FromStr,
T::Err: std::fmt::Debug,
{
let mut res = v![];
for _ in 0..n {
res.push(self.next());
}
res
}
fn next_string(&mut self) -> Option<String> {
self.buf.pop().or_else(|| match self.update() {
true => self.next_string(),
false => None,
})
}
#[inline]
fn update(&mut self) -> bool {
let mut s = String::new();
let res = self.br.read_line(&mut s);
match res.expect("I/O error.") {
0 => false,
_ => {
self.buf = s.split_whitespace().map(|x| x.to_string()).rev().collect();
true
}
}
}
}
#[test]
fn test_next() {
let mut sc = new("hoge".as_bytes());
let s: String = sc.next();
assert_eq!("hoge", s);
}
}
}
//////////////////////////////// LIBRARY END ////////////////////////////////
use contest::io::Scanner;
use contest::num::BigUint;
use contest::prelude::MyVec;
fn main() {
let mut sc = Scanner::new(std::io::stdin());
let n = sc.next::<i32>();
for _ in 0..n {
let a = sc.next::<BigUint>();
let b = sc.next::<BigUint>();
let res = format!("{}", a + b);
if res.len() > 80 {
println!("overflow");
} else {
println!("{}", res);
}
}
}