結果
問題 | No.1650 Moving Coins |
ユーザー |
![]() |
提出日時 | 2021-08-25 18:47:36 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 16,529 bytes |
コンパイル時間 | 14,823 ms |
コンパイル使用メモリ | 378,744 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 22:27:54 |
合計ジャッジ時間 | 24,349 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#![allow(unused_imports)]use pio2::*;use std::{collections::*,io::{self, prelude::*},};fn run<I: Input, O: Write>(mut pin: I, mut out: O) {let n: usize = pin.parse();let a: Vec<usize> = pin.seq(n).collect();let b: Vec<usize> = pin.seq(n).collect();let m: usize = a.iter().zip(b.iter()).map(|(x, y)| x.max(y) - x.min(y)).sum();wln!(out, "{}", m);for i in 0..n {if a[i] > b[i] {for _ in 0..a[i] - b[i] {wln!(out, "{} L", i + 1);}}}for i in (0..n).rev() {if a[i] < b[i] {for _ in 0..b[i] - a[i] {wln!(out, "{} R", i + 1);}}}}fn main() {let stdin = io::stdin();let mut pin = Scanner::new(stdin.lock());let stdout = io::stdout();let mut out = stdout.lock();run(&mut pin, &mut out);}pub mod mod_int {use std::{cmp, fmt, marker::PhantomData, ops, sync::atomic};#[macro_export]macro_rules! def_mint {($modulo:expr, $ModuloTy:ident) => {pub struct $ModuloTy;impl crate::mod_int::Modulo for $ModuloTy {fn modulo() -> u32 {$modulo}}pub type Mint = crate::mod_int::ModInt<$ModuloTy>;pub fn mint(x: u32) -> Mint {crate::mod_int::ModInt::new(x)}};}pub trait Modulo {fn modulo() -> u32;}pub struct VarMod;static VAR_MOD: atomic::AtomicU32 = atomic::AtomicU32::new(0);pub fn set_var_mod(m: u32) {VAR_MOD.store(m, atomic::Ordering::Relaxed);}impl Modulo for VarMod {fn modulo() -> u32 {VAR_MOD.load(atomic::Ordering::Relaxed)}}#[repr(transparent)]pub struct ModInt<M>(u32, PhantomData<*const M>);impl<M: Modulo> ModInt<M> {pub fn new(x: u32) -> Self {debug_assert!(x < M::modulo());Self(x, PhantomData)}pub fn normalize(self) -> Self {if self.0 < M::modulo() {self} else {Self::new(self.0 % M::modulo())}}pub fn get(self) -> u32 {self.0}pub fn inv(self) -> Self {assert_ne!(self, Self::new(0));self.pow(M::modulo() - 2)}pub fn half(self) -> Self {Self::new(self.0 / 2 + self.0 % 2 * ((M::modulo() + 1) / 2))}pub fn modulo() -> u32 {M::modulo()}}impl<M: Modulo> ops::Neg for ModInt<M> {type Output = Self;fn neg(self) -> Self {Self::new(if self.0 == 0 { 0 } else { M::modulo() - self.0 })}}impl<M: Modulo> ops::Neg for &ModInt<M> {type Output = ModInt<M>;fn neg(self) -> Self::Output {-(*self)}}impl<M: Modulo> ops::Add for ModInt<M> {type Output = Self;fn add(self, rhs: Self) -> Self {let s = self.0 + rhs.0;Self::new(if s < M::modulo() { s } else { s - M::modulo() })}}impl<M: Modulo> ops::Sub for ModInt<M> {type Output = Self;fn sub(self, rhs: Self) -> Self {Self::new(if self.0 >= rhs.0 {self.0 - rhs.0} else {M::modulo() + self.0 - rhs.0})}}impl<M: Modulo> ops::Mul for ModInt<M> {type Output = Self;fn mul(self, rhs: Self) -> Self {Self::new((self.0 as u64 * rhs.0 as u64 % M::modulo() as u64) as u32)}}impl<M: Modulo> ops::Div for ModInt<M> {type Output = Self;fn div(self, rhs: Self) -> Self {self * rhs.inv()}}macro_rules ! op_impl { ($ ($ Op : ident $ op : ident $ OpAssign : ident $ op_assign : ident) *) => { $ (impl < M : Modulo > ops ::$ Op <& Self >for ModInt < M > { type Output = Self ; fn $ op (self , rhs : & Self) -> Self { self .$ op (* rhs) } } impl < M : Modulo > ops ::$ Op <ModInt < M >> for & ModInt < M > { type Output = ModInt < M >; fn $ op (self , rhs : ModInt < M >) -> ModInt < M > { (* self) .$ op (rhs) } }impl < M : Modulo > ops ::$ Op <& ModInt < M >> for & ModInt < M > { type Output = ModInt < M >; fn $ op (self , rhs : & ModInt < M >) ->ModInt < M > { (* self) .$ op (* rhs) } } impl < M : Modulo > ops ::$ OpAssign for ModInt < M > { fn $ op_assign (& mut self , rhs : Self) {* self = ops ::$ Op ::$ op (* self , rhs) ; } } impl < M : Modulo > ops ::$ OpAssign <& ModInt < M >> for ModInt < M > { fn $ op_assign (&mut self , rhs : & ModInt < M >) { self .$ op_assign (* rhs) ; } }) * } ; }op_impl! { Add add AddAssign add_assign Sub sub SubAssign sub_assign Mul mul MulAssign mul_assign Div div DivAssign div_assign }impl<M: Modulo> std::iter::Sum for ModInt<M> {fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {iter.fold(ModInt::new(0), |x, y| x + y)}}impl<'a, M: Modulo + 'a> std::iter::Sum<&'a ModInt<M>> for ModInt<M> {fn sum<I: Iterator<Item = &'a ModInt<M>>>(iter: I) -> Self {iter.copied().sum()}}impl<M: Modulo> std::iter::Product for ModInt<M> {fn product<I: Iterator<Item = Self>>(iter: I) -> Self {iter.fold(ModInt::new(1), |x, y| x * y)}}impl<'a, M: Modulo + 'a> std::iter::Product<&'a ModInt<M>> for ModInt<M> {fn product<I: Iterator<Item = &'a ModInt<M>>>(iter: I) -> Self {iter.copied().product()}}pub trait Pow<T> {fn pow(self, n: T) -> Self;}macro_rules ! mod_int_pow_impl { ($ ($ uty : ident $ ity : ident) *) => { $ (impl < M : Modulo > Pow <$ uty > for ModInt < M > { fn pow (mut self, mut n : $ uty) -> Self { let mut y = Self :: new (1) ; while n > 0 { if n & 1 == 1 { y *= self ; } self *= self ; n /= 2 ; } y } } impl < M: Modulo > Pow <$ ity > for ModInt < M > { fn pow (self , n : $ ity) -> Self { if n >= 0 { self . pow (n as $ uty) } else { self . inv () .pow (- n as $ uty) } } }) * } ; }mod_int_pow_impl ! (usize isize u32 i32 u64 i64);macro_rules ! mod_int_from_impl { ($ ($ T : ident) *) => { $ (impl < M : Modulo > From <$ T > for ModInt < M > { # [allow (unused_comparisons)]fn from (x : $ T) -> Self { if M :: modulo () <= $ T :: max_value () as u32 { Self :: new (x . rem_euclid (M :: modulo () as $ T) as u32) }else if x < 0 { Self :: new ((M :: modulo () as i32 + x as i32) as u32) } else { Self :: new (x as u32) } } }) * } }mod_int_from_impl ! (isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128);impl<M: Modulo> From<bool> for ModInt<M> {fn from(x: bool) -> Self {Self::new(x as u32)}}impl<M> Copy for ModInt<M> {}impl<M> Clone for ModInt<M> {fn clone(&self) -> Self {*self}}impl<M: Modulo> Default for ModInt<M> {fn default() -> Self {Self::new(0)}}impl<M> cmp::PartialEq for ModInt<M> {fn eq(&self, other: &Self) -> bool {self.0 == other.0}}impl<M> cmp::Eq for ModInt<M> {}impl<M> cmp::PartialOrd for ModInt<M> {fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {self.0.partial_cmp(&other.0)}}impl<M> cmp::Ord for ModInt<M> {fn cmp(&self, other: &Self) -> cmp::Ordering {self.0.cmp(&other.0)}}impl<M> std::hash::Hash for ModInt<M> {fn hash<H: std::hash::Hasher>(&self, state: &mut H) {self.0.hash(state);}}impl<M> fmt::Display for ModInt<M> {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {self.0.fmt(f)}}impl<M> fmt::Debug for ModInt<M> {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {self.0.fmt(f)}}}pub mod macros {#[macro_export]macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }#[macro_export]macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { 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]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) ,*) => { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) } ; }}pub mod pio2 {use std::{io::prelude::*,marker::PhantomData,mem::{self, MaybeUninit},str,};pub trait Input {fn bytes(&mut self) -> &[u8];#[inline]fn str(&mut self) -> &str {str::from_utf8(self.bytes()).unwrap()}#[inline]fn parse<T>(&mut self) -> TwhereDefaultParser: Parser<T>,{self.parse_with(DefaultParser)}#[inline]fn parse_with<T, P: Parser<T>>(&mut self, mut parser: P) -> T {parser.parse(self)}#[inline]fn seq<T>(&mut self, n: usize) -> Seq<Self, T, DefaultParser>whereDefaultParser: Parser<T>,{self.seq_with(n, DefaultParser)}#[inline]fn seq_with<T, P: Parser<T>>(&mut self, n: usize, parser: P) -> Seq<Self, T, P> {Seq {src: self,rest: n,parser,phantom: PhantomData,}}}impl<I: Input> Input for &mut I {#[inline]fn bytes(&mut self) -> &[u8] {(**self).bytes()}}pub struct Scanner<R> {src: R,buf: Vec<u8>,pos: usize,len: usize,}impl<R: Read> Scanner<R> {#[inline]pub fn new(src: R) -> Self {Self {src,buf: vec![0; 1 << 16],pos: 0,len: 0,}}fn read(&mut self) -> usize {if self.pos > 0 {self.buf.copy_within(self.pos..self.len, 0);self.len -= self.pos;self.pos = 0;} else if self.len >= self.buf.len() {self.buf.resize(2 * self.buf.len(), 0);}let n = self.src.read(&mut self.buf[self.len..]).unwrap();self.len += n;assert!(self.len <= self.buf.len());n}}impl<R: Read> Input for Scanner<R> {fn bytes(&mut self) -> &[u8] {loop {while let Some(d) = unsafe { self.buf.get_unchecked(self.pos..self.len) }.iter().position(u8::is_ascii_whitespace){let p = self.pos;self.pos += d + 1;if d > 0 {return unsafe { self.buf.get_unchecked(p..p + d) };}}if self.read() == 0 {let p = self.pos;if p == self.len {panic!("reached EOF");}self.pos = self.len;return unsafe { self.buf.get_unchecked(p..self.len) };}}}}pub struct Seq<'a, I: ?Sized, T, P> {src: &'a mut I,rest: usize,parser: P,phantom: PhantomData<*const T>,}impl<'a, I: Input + ?Sized, T, P: Parser<T>> Iterator for Seq<'a, I, T, P> {type Item = T;#[inline]fn next(&mut self) -> Option<T> {if self.rest > 0 {self.rest -= 1;Some(self.src.parse_with(&mut self.parser))} else {None}}#[inline]fn size_hint(&self) -> (usize, Option<usize>) {(self.rest, Some(self.rest))}}impl<'a, I: Input + ?Sized, T, P: Parser<T>> ExactSizeIterator for Seq<'a, I, T, P> {}pub trait Parser<T> {fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T;}impl<T, P: Parser<T>> Parser<T> for &mut P {#[inline]fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T {(*self).parse(src)}}#[derive(Clone, Copy, Debug)]pub struct DefaultParser;macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; }macro_rules! int {($ty:ty) => {impl Parser<$ty> for DefaultParser {#[inline]fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty);let s = src.bytes();if let Some((&b'-', t)) = s.split_first() {-f(t)} else {f(s)}}}};}impls!(int, isize, i8, i16, i32, i64, i128);macro_rules! uint {($ty:ty) => {impl Parser<$ty> for DefaultParser {#[inline]fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty)}}};}impls!(uint, usize, u8, u16, u32, u64, u128);macro_rules! from_bytes {($ty:ty) => {impl Parser<$ty> for DefaultParser {#[inline]fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {src.bytes().into()}}};}impls!(from_bytes, Vec<u8>, Box<[u8]>);macro_rules! from_str {($ty:ty) => {impl Parser<$ty> for DefaultParser {#[inline]fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {src.str().parse::<$ty>().expect("failed to parse")}}};}impls!(from_str, String, char, f32, f64);macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T) ,+> Parser < ($ ($ T ,) +) > for DefaultParser where $ (DefaultParser : Parser <$ T>) ,+ { # [inline] fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> ($ ($ T ,) +) { ($ (< Self as Parser <$ T >>:: parse(self , 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);macro_rules ! array { ($ ($ N : literal) *) => { $ (impl < T > Parser < [T ; $ N] > for DefaultParser where DefaultParser : Parser < T > { fnparse < I : Input + ? Sized > (& mut self , src : & mut I) -> [T ; $ N] { unsafe { let mut arr : [MaybeUninit < T >; $ N] = MaybeUninit ::uninit () . assume_init () ; for elem in & mut arr { * elem = MaybeUninit :: new (src . parse ()) ; } mem :: transmute_copy (& arr) } } }) *} }array ! (1 2 3 4 5 6 7 8);}