結果
| 問題 |
No.381 名声値を稼ごう Extra
|
| コンテスト | |
| ユーザー |
 rakic Lynd
|
| 提出日時 | 2025-11-11 16:53:21 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 5,156 ms / 8,000 ms |
| コード長 | 19,992 bytes |
| コンパイル時間 | 12,351 ms |
| コンパイル使用メモリ | 398,592 KB |
| 実行使用メモリ | 7,712 KB |
| 最終ジャッジ日時 | 2025-11-11 16:53:40 |
| 合計ジャッジ時間 | 18,605 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 |
ソースコード
#![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 {
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);
impl BigUint {
pub fn count_ones(&self) -> u32 {
self.data.iter().fold(0, |acc, x| acc + x.count_ones())
}
}
#[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);
}
// （中间测试保持不变）
}
}
}
#[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()]
}
}
}
}
#[macro_use]
pub mod io {
use std;
use std::io;
use std::io::BufRead;
use super::prelude::MyVec;
pub struct Scanner<R: io::Read> {
br: io::BufReader<R>,
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
}
}
}
}
}
}
//////////////////////////////// LIBRARY END ////////////////////////////////
use contest::io::Scanner;
use contest::num::BigUint;
use contest::prelude::MyVec;
fn main() {
let mut sc = Scanner::new(std::io::stdin());
// AOJ National Budget
// 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);
// }
// }
// yukicoder 381
let i = sc.next::<BigUint>();
println!("{}", i.count_ones());
}