結果
| 問題 | No.3395 Range Flipping Game |
| コンテスト | |
| ユーザー |
👑  Mizar
|
| 提出日時 | 2025-12-02 01:50:33 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 14 ms / 2,000 ms |
| コード長 | 11,902 bytes |
| コンパイル時間 | 13,105 ms |
| コンパイル使用メモリ | 397,140 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-12-02 01:50:50 |
| 合計ジャッジ時間 | 15,524 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 30 |
ソースコード
// -*- coding:utf-8-unix -*-
pub fn solve() -> std::io::Result<()> {
let mut bw = FBufWriter::new(std::io::stdout().lock());
input! {
t: usize,
}
for _ in 0..t {
input! {
n: usize,
mut s: Bytes,
}
if n == 1 {
bw.bytes_ln(b"B")?;
continue;
}
match [s[0],s[1]] {
[b'B', b'B'] => {}
[b'A', b'B'] => {
s[0] = b'B';
let mut it = s.iter().enumerate().skip(2);
let (mut i, mut j) = (0usize, 0usize);
while let Some((k, &c)) = it.next() {
if c == b'B' {
i = k;
j = n;
break;
}
}
while let Some((k, &c)) = it.next() {
if c == b'A' {
j = k;
break;
}
}
s[i..j].fill(b'A');
}
_ => {
s[0] = b'B';
s[1] = b'B';
let mut j = n;
let mut it = s.iter().enumerate().skip(2);
while let Some((k, &c)) = it.next() {
if c == b'A' {
j = k;
break;
}
}
s[2..j].fill(b'A');
}
}
bw.bytes_ln(&s)?;
}
// AAA ABA BBA
// AAB ABA BBA
// ABA ABA BBA
// ABB ABA BBA
// BAB ABA BBA
// BAA ABA BBA
// BBA ABA BAA
// BBBA ABBA BBBA
// BBBA BBAB
bw.flush()?;
Ok(())
}
#[allow(unused)]
use std::{cmp::*, collections::*, hash::BuildHasherDefault};
fn main() -> std::io::Result<()> {
const USE_THREAD: bool = false;
if USE_THREAD {
// In order to avoid potential stack overflow, spawn a new thread.
let stack_size = 134_217_728; // 128 MB
let thd = std::thread::Builder::new().stack_size(stack_size);
thd.spawn(|| solve()).unwrap().join().unwrap()
} else {
solve()
}
}
#[allow(unused)]
use {ichange::*, ifastout::*, iinput_lite::*, iinvariant::*};
#[rustfmt::skip]#[allow(unused)]mod ichange{pub trait Change{fn chmax(&mut self,x:Self)->bool;fn chmin(&mut self,x:Self)->bool;}impl<T:PartialOrd>Change for T{fn chmax(&mut self,x:T)->bool{if*self<x{*self=x;true}else{false}}fn chmin(&mut self,x:T)->bool{if*self>x{*self=x;true}else{false}}}}
#[rustfmt::skip]#[allow(unused)]mod iinvariant{#[macro_export]macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}}
#[rustfmt::skip]#[allow(unused)]mod iinput_lite{#[macro_export]macro_rules!read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0])};($b:expr,Bytes)=>{token($b,|s|s.to_vec())};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).ok().map(|s|s.chars().collect::<Vec<_>>()))};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,Usize1)=>{read_value!($b,usize)-1};($b:expr,Isize1)=>{read_value!($b,isize)-1};($b:expr,$t:ty)=>{token($b,|s|{std::str::from_utf8(s).unwrap().parse::<$t>().unwrap()})};}#[macro_export]macro_rules!input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,mut$var:ident:$t:tt$($r:tt)*)=>{let mut$var=read_value!($b,$t);input_inner!{$b$($r)*}};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}#[macro_export]macro_rules!input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T)->T{let(b,l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&c|!c.is_ascii_whitespace()){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some(p)=b.iter().position(|&c|c.is_ascii_whitespace()){let t=&b[..p];let x=f(t);r.consume(l+p+1);return x;}let mut t=b.to_vec();r.consume(l+t.len());while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&c|c.is_ascii_whitespace()){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}f(&t)}}
#[rustfmt::skip]#[allow(unused)]mod ifastout{use std::*;pub use io::Write;use ptr::copy_nonoverlapping as c;type R=io::Result<()>;type P=*mut u8;const O4:u64=10000;const O8:u64=O4*O4;const O16:u64=O8*O8;const H32:u128=10u128.pow(32);macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){unsafe{hint::unreachable_unchecked()}}};}const LP:[u32;10000]={let(mut x,mut i)=([0u32;10000],0);while i<10000{let(a,b,c,d)=(i/1000,i/100%10,i/10%10,i%10);x[i as usize]=0x30303030|a|(b<<8)|(c<<16)|(d<<24);i+=1;}x};const LS:[u32;10000]={let(mut x,mut i)=([0u32;10000],0);while i<10000{let(a,b,c,d)=(i/1000,i/100%10,i/10%10,i%10);x[i as usize]=match i{0..=9=>0x30|d,10..=99=>0x3030|c|(d<<8),100..=999=>0x303030|b|(c<<8)|(d<<16),_=>0x30303030|a|(b<<8)|(c<<16)|(d<<24),};i+=1;}x};#[inline]unsafe fn d4(v:&mut P,x:u64){invariant!(x<O4);c(LP[x as usize].to_le_bytes().as_ptr(),*v,4);*v=v.add(4)}#[inline]unsafe fn d4l(v:&mut P,x:u64){invariant!(x<O4);c(LS[x as usize].to_le_bytes().as_ptr(),*v,4);*v=v.add(1+(x>9)as usize+(x>99)as usize+(x>999)as usize);}#[inline]unsafe fn d8(v:&mut P,x:u64){invariant!(x<O8);let(y0,y1)=drq4(x);d4(v,y0);d4(v,y1)}#[inline]unsafe fn d16(v:&mut P,x:u64){invariant!(x<O16);let(y0,y1)=dro8(x);d8(v,y0);d8(v,y1)}#[inline]unsafe fn d8l(v:&mut P,x:u64){invariant!(x<O8);if x<O4{d4l(v,x)}else{let(y0,y1)=drq4(x as _);d4l(v,y0);d4(v,y1)}}#[inline]unsafe fn d16l(v:&mut P,x:u64){invariant!(x<O16);if x<O8{d8l(v,x)}else{let(y0,y1)=dro8(x);d8l(v,y0);d8(v,y1)}}#[inline]pub unsafe fn du8(v:&mut P,x:u8){d4l(v,x as _)}#[inline]pub unsafe fn du16(v:&mut P,x:u16){d8l(v,x as _)}#[inline]pub unsafe fn du32(v:&mut P,x:u32){if x<O8 as _{d8l(v,x as _)}else{let(y0,y1)=drq8(x as _);invariant!(y0<43);d4l(v,y0);d8(v,y1)}}#[inline]pub unsafe fn du64(v:&mut P,x:u64){if x<O16{d16l(v,x)}else{let(y0,y1)=dro16(x);invariant!(y0<1845);d4l(v,y0);d16(v,y1)}}#[inline]pub unsafe fn dusize(v:&mut P,x:usize){du64(v,u64::try_from(x).unwrap())}#[inline]fn drh_16(x:u128)->(u64,u64){invariant!(x<0xd8e03efa8ff0175cfffffffff0000);let q=((((x>>52)as u64)as u128*8307674973655724205)>>64)as u64;let r=(x as u64).wrapping_sub(q.wrapping_mul(O16));if let Some(s)=r.checked_sub(O16){(q+1,s)}else{(q,r)}}const O19:u64=1000*O16;const H19:u128=O19 as _;#[inline]unsafe fn d3(v:&mut P,x:u64){invariant!(x<1000);c((LP[x as usize]>>8).to_le_bytes().as_ptr(),*v,4);*v=v.add(3);}#[inline]unsafe fn d19(v:&mut P,x:u64){invariant!(x<O19);let(y0,y1)=dro16(x);d3(v,y0);d16(v,y1);}#[inline]fn drh19(x:u128)->(u64,u64){invariant!(x>>64<H19);let q=((x>>64)*17014118346046923173>>64)as u64;let r=((x>>19)as u64).wrapping_sub(q.wrapping_mul(O19>>18));let s=(r as u128*519229685853483>>93)as u64;(q*2+s,(x as u64&0x7ffff)|(r<<19).wrapping_sub(O19*s))}#[inline]fn dro16(x:u64)->(u64,u64){let q=(x as u128*4153837486827862103>>115)as u64;(q,x-q*O16)}#[inline]fn dro8(x:u64)->(u64,u64){invariant!(x<O16);let q=(x as u128*12379400392853802749>>90)as u64;(q,x-q*O8)}#[inline]fn drq8(x:u64)->(u64,u64){invariant!(x>>32==0);let q=(x as u128*184467440738>>64)as u64;(q,x-q*O8)}#[inline]fn drq4(x:u64)->(u64,u64){invariant!(x<O8);let q=(x as u128*1844674407370956>>64)as u64;(q,x-q*O4)}#[inline]pub unsafe fn du128(v:&mut P,x:u128){if x<=u64::MAX as u128{du64(v,x as u64)}else if(x>>64)<H19{let(y0,y1)=drh19(x);du64(v,y0);d19(v,y1);}else{let mut y0=(((x>>64)*3402823)>>64)as u64;let mut y1=x-y0 as u128*H32;if let Some(yt)=y1.checked_sub(H32){y1=yt;y0+=1;}invariant!(702<y0&&y0<3402824);d8l(v,y0);let(z0,z1)=drh_16(y1);d16(v,z0);d16(v,z1)}}#[inline]unsafe fn dmn(v:&mut*mut u8){**v=b'-';*v=(*v).add(1)}macro_rules!imi{($i:ident,$u:ident,$t:ty)=>{#[inline]pub unsafe fn$i(v:&mut P,x:$t){if x<0{dmn(v);}$u(v,x.unsigned_abs());}};}imi!(di8,du8,i8);imi!(di16,du16,i16);imi!(di32,du32,i32);imi!(di64,du64,i64);imi!(disize,dusize,isize);imi!(di128,du128,i128);macro_rules!imf{($f:ident,$spf:ident,$fsp:ident,$fln:ident,$fv:ident,$ty:ty,$d:ident)=>{#[inline]pub fn$f<U:Into<$ty>>(&mut self,x:U)->R{unsafe{$d(&mut self.p,x.into());}if self.p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$spf<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{*p=b' ';p=p.add(1);$d(&mut p,x.into());}self.p=p;if p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$fsp<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{$d(&mut p,x.into());*p=b' ';p=p.add(1);}self.p=p;if p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$fln<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{$d(&mut p,x.into());*p=b'\n';p=p.add(1);}self.p=p;if p>=self.limit{self.flush()?}Ok(())}pub fn$fv<U:Copy+Into<$ty>>(&mut self,x:&[U])->R{if!x.is_empty(){self.$f(x[0])?;for&y in x[1..].iter(){self.$spf(y)?;}}unsafe{*self.p=b'\n';self.p=self.p.add(1);}if self.p>=self.limit{self.flush()?}Ok(())}};}const SBUF:usize=65536;const SLIM:usize=SBUF-48;pub struct FBufWriter<W:Write>{inner:Option<W>,buf:Box<[mem::MaybeUninit<u8>;SBUF]>,limit:*mut u8,p:*mut u8,}impl<W:Write>Write for FBufWriter<W>{fn write(&mut self,b:&[u8])->io::Result<usize>{let bl=b.len();let space=unsafe{self.limit.offset_from(self.p)as usize};if bl<=SBUF-SLIM{unsafe{c(b.as_ptr(),self.p,bl);self.p=self.p.add(bl);}if self.p>self.limit{self.flush()?}}else if SLIM<bl{self.flush()?;self.inner.as_mut().unwrap().write_all(b)?}else if space<bl{unsafe{c(b.as_ptr(),self.p,space);self.p=self.limit;}self.flush()?;let b=&b[space..];unsafe{c(b.as_ptr(),self.p,b.len());self.p=self.p.add(b.len())}}else{unsafe{c(b.as_ptr(),self.p,bl);self.p=self.p.add(bl)}}Ok(bl)}fn flush(&mut self)->io::Result<()>{let base=self.buf.as_mut_ptr()as*mut u8;if self.p>base{unsafe{let len=self.p.offset_from(base)as usize;self.inner.as_mut().unwrap().write_all(slice::from_raw_parts(base,len))?;self.p=base;}}Ok(())}}impl<W:Write>Drop for FBufWriter<W>{fn drop(&mut self){let _=self.flush();}}impl<W:Write>FBufWriter<W>{pub fn new(inner:W)->Self{let mut buf=Box::new([mem::MaybeUninit::uninit();SBUF]);unsafe{let base=buf.as_mut_ptr()as*mut u8;FBufWriter{inner:Some(inner),buf,limit:base.add(SLIM),p:base,}}}pub fn into_inner(mut self)->W{self.flush().unwrap();self.inner.take().unwrap()}imf!(u8,sp_u8,u8_sp,u8_ln,u8v,u8,du8);imf!(u16,sp_u16,u16_sp,u16_ln,u16v,u16,du16);imf!(u32,sp_u32,u32_sp,u32_ln,u32v,u32,du32);imf!(u64,sp_u64,u64_sp,u64_ln,u64v,u64,du64);imf!(usize,sp_usize,usize_sp,usize_ln,usizev,usize,dusize);imf!(u128,sp_u128,u128_sp,u128_ln,u128v,u128,du128);imf!(u,sp_u,u_sp,u_ln,uv,u128,du128);imf!(i8,sp_i8,i8_sp,i8_ln,i8v,i8,di8);imf!(i16,sp_i16,i16_sp,i16_ln,i16v,i16,di16);imf!(i32,sp_i32,i32_sp,i32_ln,i32v,i32,di32);imf!(i64,sp_i64,i64_sp,i64_ln,i64v,i64,di64);imf!(isize,sp_isize,isize_sp,isize_ln,isizev,isize,disize);imf!(i128,sp_i128,i128_sp,i128_ln,i128v,i128,di128);imf!(i,sp_i,i_sp,i_ln,iv,i128,di128);#[inline]pub fn byte(&mut self,b:u8)->R{unsafe{*self.p=b;self.p=self.p.add(1);}if self.p>self.limit{self.flush()?;}Ok(())}#[inline]fn sbytes(&mut self,b:&[u8])->R{invariant!(b.len()<=SBUF-SLIM);unsafe{c(b.as_ptr(),self.p,b.len());self.p=self.p.add(b.len());}if self.p>self.limit{self.flush()?;}Ok(())}#[inline]pub fn bytes(&mut self,b:&[u8])->R{self.write(b).map(|_|())}pub fn bytes_ln(&mut self,b:&[u8])->R{self.bytes(b)?;self.ln()}#[inline]pub fn str(&mut self,s:&str)->R{self.bytes(s.as_bytes())}#[inline]pub fn sp(&mut self)->R{self.byte(b' ')}#[inline]pub fn ln(&mut self)->R{self.byte(b'\n')}#[inline]pub fn yes(&mut self,x:bool)->R{if x{self.sbytes(b"Yes")}else{self.sbytes(b"No")}}#[inline]pub fn yes_ln(&mut self,x:bool)->R{if x{self.sbytes(b"Yes\n")}else{self.sbytes(b"No\n")}}}}