結果

問題 No.1650 Moving Coins
ユーザー cotton_fn_cotton_fn_
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![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) -> T
where
DefaultParser: 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>
where
DefaultParser: 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 > { fn
        parse < 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0