結果
問題 | No.2479 Sum of Squares |
ユーザー |
![]() |
提出日時 | 2023-09-22 22:50:11 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,379 ms / 2,000 ms |
コード長 | 17,198 bytes |
コンパイル時間 | 11,304 ms |
コンパイル使用メモリ | 402,180 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-08 13:34:15 |
合計ジャッジ時間 | 20,629 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:15:9 | 15 | let mut r = (n as f64).sqrt() as i64 + 1; | ----^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: function `find_ws_naive` is never used --> src/main.rs:168:19 | 168 | pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> { | ^^^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#![allow(unused_imports)]use input2::*;use std::{collections::*,io::{self, BufWriter, Read, Write},};fn run<I: Read, O: Write>(mut ss: Input<I>, mut out: O) {let t: u32 = 1;for _ in 0..t {case(&mut ss, &mut out);}}fn case<I: Read, O: Write>(ss: &mut Input<I>, mut out: O) {let mut n = ss.i64();let mut r = (n as f64).sqrt() as i64 + 1;let mut ans = vec![];for i in (1..=r).rev() {while i * i <= n {ans.push(i * i);n -= i * i;}}wln!(out, "{}", ans.len());w_iter_ln!(out, "{}", ans);}fn main() {let stdin = io::stdin();let ss = Input::new(stdin.lock());let stdout = io::stdout();let out = BufWriter::new(stdout.lock());run(ss, out);}pub mod input2 {use std::{convert::TryInto,io::{self, Read},marker::PhantomData,mem::{self, MaybeUninit},ptr, slice,};pub struct Input<R> {src: R,buf: Vec<u8>,pos: usize,len: usize,}macro_rules! def_input {($ ty : ident) => {pub fn $ty(&mut self) -> $ty {self.input()}};}impl<R: Read> Input<R> {pub fn new(src: R) -> Self {Self::with_capacity(src, 1 << 20)}pub fn with_capacity(src: R, cap: usize) -> Self {Self {src,buf: vec![0; cap],pos: 0,len: 0,}}pub fn input<T: Parse>(&mut self) -> T {T::parse(self)}pub fn seq<T: Parse>(&mut self, n: usize) -> Seq<T, R> {Seq {src: self,n,marker: PhantomData,}}pub fn vec<T: Parse>(&mut self, n: usize) -> Vec<T> {self.seq(n).collect()}pub fn str(&mut self) -> &str {std::str::from_utf8(self.bytes()).expect("utf8 error")}pub fn bytes(&mut self) -> &[u8] {let range = self.bytes_inner();unsafe { self.buf.get_unchecked(range) }}pub fn bytes_vec(&mut self) -> Vec<u8> {let range = self.bytes_inner();if range.start == 0 && 2 * range.end >= self.buf.len() {let buf_len = self.buf.len();let mut new_buf = vec![0; buf_len];new_buf[..self.len].copy_from_slice(self.remaining());let mut res = mem::replace(&mut self.buf, new_buf);self.pos = 0;res.truncate(range.end);res} else {self.buf[range].to_vec()}}#[inline]fn bytes_inner(&mut self) -> std::ops::Range<usize> {let mut i = 0;loop {if self.len > 0 {if let Some(d) = find_ws(unsafe {self.buf.get_unchecked(self.pos + i..self.pos + self.len)}) {let del = i + d;let range = self.pos..self.pos + del;self.pos += del + 1;self.len -= del + 1;if del == 0 {continue;}return range;}i = self.len;}if self.read() == 0 {let range = self.pos..self.pos + self.len;self.pos = 0;self.len = 0;return range;}}}#[cold]fn read(&mut self) -> usize {if self.pos != 0 {self.buf.copy_within(self.pos..self.pos + self.len, 0);self.pos = 0;}if self.len == self.buf.len() {self.buf.resize(2 * self.buf.len(), 0);}loop {match self.src.read(unsafe { self.buf.get_unchecked_mut(self.len..) }){Ok(n) => {self.len += n;return n;}Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}Err(e) => panic!("io error: {}", e),}}}#[inline]fn remaining(&self) -> &[u8] {unsafe { self.buf.get_unchecked(self.pos..self.pos + self.len) }}def_input!(usize);def_input!(u8);def_input!(u16);def_input!(u32);def_input!(u64);def_input!(isize);def_input!(i8);def_input!(i16);def_input!(i32);def_input!(i64);def_input!(f32);def_input!(f64);}#[inline]pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> {for (i, c) in s.iter().enumerate() {if *c <= b' ' {return Some(i);}}None}const CHUNK_SIZE: usize = mem::size_of::<usize>();#[inline]pub(crate) fn find_ws(s: &[u8]) -> Option<usize> {let offset = (32 + s.as_ptr().align_offset(CHUNK_SIZE)).min(s.len());let mut i = 0;while i < offset {if s[i] <= b' ' {return Some(i);}i += 1;}if i < s.len() {find_ws_long(s, i)} else {None}}fn find_ws_long(s: &[u8], mut i: usize) -> Option<usize> {while i + CHUNK_SIZE <= s.len() {if let Some(j) = find_ws_usize(usize::from_le_bytes(unsafe { s.get_unchecked(i..i + CHUNK_SIZE) }.try_into().unwrap(),)) {return Some(i + j);}i += CHUNK_SIZE;}while i < s.len() {if s[i] <= b' ' {return Some(i);}i += 1;}None}#[inline]fn find_ws_usize(s: usize) -> Option<usize> {const SUB: usize = 0x2121212121212121;const MASK: usize = 0x8080808080808080;let t = s.wrapping_sub(SUB) & MASK;(t != 0).then(|| (t.trailing_zeros() / 8) as usize)}pub struct Seq<'a, T, R> {src: &'a mut Input<R>,n: usize,marker: PhantomData<*const T>,}impl<'a, T: Parse, R: Read> Iterator for Seq<'a, T, R> {type Item = T;fn next(&mut self) -> Option<Self::Item> {if self.n > 0 {self.n -= 1;Some(self.src.input())} else {None}}fn size_hint(&self) -> (usize, Option<usize>) {(self.n, Some(self.n))}}impl<'a, T: Parse, R: Read> ExactSizeIterator for Seq<'a, T, R> {fn len(&self) -> usize {self.size_hint().0}}pub trait Parse {fn parse<T: Read>(src: &mut Input<T>) -> Self;}impl Parse for Vec<u8> {fn parse<T: Read>(src: &mut Input<T>) -> Self {src.bytes_vec()}}impl Parse for String {fn parse<T: Read>(src: &mut Input<T>) -> Self {String::from_utf8(src.bytes_vec()).unwrap()}}pub trait ParseBytes {fn parse_bytes(s: &[u8]) -> Self;}macro_rules! parse_int {($ ty : ident , $ ity : ident) => {impl ParseBytes for $ty {fn parse_bytes(s: &[u8]) -> Self {$ty(s, 0)}}impl ParseBytes for $ity {fn parse_bytes(s: &[u8]) -> Self {let (minus, s) = if let Some((b'-', s)) = s.split_first() {(true, s)} else {(false, s)};let x = $ty(s, 0);(if minus { (!x).wrapping_add(1) } else { x }) as $ity}}};}parse_int!(usize, isize);parse_int!(u8, i8);parse_int!(u16, i16);parse_int!(u32, i32);parse_int!(u64, i64);macro_rules! parse {($ ty : ident) => {impl Parse for $ty {fn parse<T: Read>(src: &mut Input<T>) -> Self {Self::parse_bytes(src.bytes())}}};}parse!(usize);parse!(u8);parse!(u16);parse!(u32);parse!(u64);parse!(isize);parse!(i8);parse!(i16);parse!(i32);parse!(i64);parse!(f32);parse!(f64);macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T : Parse) ,+> Parse for ($ ($ T ,) +) { fn parse < T : Read > (src : & mut Input < T>) -> Self { ($ ($ T :: parse (src) ,) +) } } } ; }tuple!(A);tuple!(A, B);tuple!(A, B, C);tuple!(A, B, C, D);tuple!(A, B, C, D, E);tuple!(A, B, C, D, E, F);tuple!(A, B, C, D, E, F, G);tuple!(A, B, C, D, E, F, G, H);impl<T: Parse, const N: usize> Parse for [T; N] {fn parse<R: Read>(src: &mut Input<R>) -> Self {struct Guard<T> {ptr: *mut T,i: usize,}impl<T> Drop for Guard<T> {fn drop(&mut self) {unsafe {ptr::drop_in_place(slice::from_raw_parts_mut(self.ptr, self.i));}}}let mut res: MaybeUninit<[T; N]> = MaybeUninit::uninit();let mut g = Guard {ptr: res.as_mut_ptr() as *mut T,i: 0,};unsafe {while g.i < N {g.ptr.add(g.i).write(src.input());g.i += 1;}mem::forget(g);res.assume_init()}}}#[inline]fn toi8bytes(s: &[u8]) -> (u32, &[u8]) {let (p, rest) = s.split_at(8);let x = u64::from_le_bytes(p.try_into().unwrap());const MASK1: u64 = 0x000f000f000f000f;let hi = (x >> 8) & MASK1;let lo = x & MASK1;let x = 10 * lo + hi;const MASK2: u64 = 0x0000ffff0000ffff;let hi = (x >> 16) & MASK2;let lo = x & MASK2;let x = 100 * lo + hi;let hi = (x >> 32) as u32;let lo = x as u32;let x = 10000 * lo + hi;(x, rest)}#[inline]fn toi4bytes(s: &[u8]) -> (u32, &[u8]) {let (p, rest) = s.split_at(4);let x = u32::from_le_bytes(p.try_into().unwrap());const MASK: u32 = 0x000f000f;let hi = (x >> 8) & MASK;let lo = x & MASK;let x = 10 * lo + hi;let hi = x >> 16;let lo = x & 0x0000ffff;let x = 100 * lo + hi;(x, rest)}#[cfg(target_pointer_width = "32")]fn usize(s: &[u8], pre: usize) -> usize {u32(s, pre as u32) as usize}#[cfg(target_pointer_width = "64")]fn usize(s: &[u8], pre: usize) -> usize {u64(s, pre as u64) as usize}#[inline]fn u64(mut s: &[u8], pre: u64) -> u64 {let mut res = pre;while s.len() >= 8 {let (x, rest) = toi8bytes(s);res = 100000000 * res + x as u64;s = rest;}if s.len() >= 4 {let (x, rest) = toi4bytes(s);res = 10000 * res + x as u64;s = rest;}for &c in s {res = 10 * res + (c & 0xf) as u64;}res}#[inline]fn u32(mut s: &[u8], pre: u32) -> u32 {let mut res = pre;if s.len() >= 8 {let (x, rest) = toi8bytes(s);res = x;s = rest;}if s.len() >= 4 {let (x, rest) = toi4bytes(s);res = 10000 * res + x;s = rest;}for &c in s {res = 10 * res + (c & 0xf) as u32;}res}#[inline]fn u16(mut s: &[u8], pre: u16) -> u16 {let mut res = pre;if s.len() >= 4 {let (x, rest) = toi4bytes(s);res = 10000 * res + x as u16;s = rest;}for &c in s {res = 10 * res + (c & 0xf) as u16;}res}#[inline]fn u8(s: &[u8], pre: u8) -> u8 {let mut res = pre;for &c in s {res = 10 * res + (c & 0xf);}res}macro_rules! float {($ ty : ident , $ uty : ident) => {impl ParseBytes for $ty {fn parse_bytes(s: &[u8]) -> Self {const TEN: [$ty; 18] = [1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,1e14, 1e15, 1e16, 1e17,];let (minus, s) = if let Some((b'-', s)) = s.split_first() {(true, s)} else {(false, s)};let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {(&s[..p], &s[p + 1..])} else {(s, &s[..0])};let x = $uty(int, 0);let x = if fract.is_empty() {x as $ty} else {let ten = TEN.get(fract.len()).copied().unwrap_or_else(|| $ty::powi(10.0, fract.len() as _));$uty(fract, x) as $ty / ten};if minus {-x} else {x}}}};}float!(f32, u32);float!(f64, u64);impl Parse for char {fn parse<T: Read>(src: &mut Input<T>) -> Self {let s = src.str();let mut cs = s.chars();match cs.next() {Some(c) if cs.as_str().is_empty() => c,_ => panic!("input is not single char"),}}}pub struct Byte(pub u8);impl Parse for Byte {fn parse<T: Read>(src: &mut Input<T>) -> Self {if let [b] = src.bytes() {Byte(*b)} else {panic!("input is not single byte")}}}}pub mod macros {extern "C" {pub fn isatty(fd: i32) -> i32;}#[macro_export]macro_rules ! w { ($ dst : expr , $ ($ arg : tt) *) => { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write !($ dst , "\x1B[1;33m") . unwrap () ; write ! ($ dst , $ ($ arg) *) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { write !($ dst , $ ($ arg) *) . unwrap () ; } } }#[macro_export]macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0{ write ! ($ dst , "\x1B[1;33m") . unwrap () ; writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ;} else { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; } # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }#[macro_export]macro_rules! w_iter {($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{let mut first = true;for elem in $iter {if first {w!($dst, $fmt, elem);first = false;} else {w!($dst, concat!($delim, $fmt), elem);}}}};($ dst : expr , $ fmt : expr , $ iter : expr) => {w_iter!($dst, $fmt, $iter, " ")};}#[macro_export]macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }#[macro_export]macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }#[macro_export]macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }#[macro_export]#[doc(hidden)]macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat !(__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }#[macro_export]macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*), file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }}