QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#836055 | #9925. LR String | ucup-team296# | WA | 25ms | 2232kb | Rust | 21.2kb | 2024-12-28 16:16:57 | 2024-12-28 16:16:58 |
Judging History
answer
// https://contest.ucup.ac/contest/1885/problem/9925
use crate::algo_lib::collections::vec_ext::gen::VecGen;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::misc::test_type::TaskType;
use crate::algo_lib::misc::test_type::TestType;
use crate::algo_lib::string::str::StrReader;
type PreCalc = ();
fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &mut PreCalc) {
let s = input.read_str();
let next_l = Vec::gen_back(
s.len() + 1,
|i, n| { if i >= s.len() { i } else if s[i] == b'L' { i } else { n[i + 1] } },
);
let next_r = Vec::gen_back(
s.len() + 1,
|i, n| { if i >= s.len() { i } else if s[i] == b'R' { i } else { n[i + 1] } },
);
let q = input.read_size();
for _ in 0..q {
let t = input.read_str();
let mut at = 0;
for c in t {
if at >= s.len() {
at += 1;
break;
}
if c == b'L' {
at = next_l[at] + 1;
} else {
at = next_r[at] + 1;
}
}
out.print_line(at <= s.len());
}
}
pub static TEST_TYPE: TestType = TestType::MultiNumber;
pub static TASK_TYPE: TaskType = TaskType::Classic;
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
let mut pre_calc = ();
match TEST_TYPE {
TestType::Single => solve(&mut input, &mut output, 1, &mut pre_calc),
TestType::MultiNumber => {
let t = input.read();
for i in 1..=t {
solve(&mut input, &mut output, i, &mut pre_calc);
}
}
TestType::MultiEof => {
let mut i = 1;
while input.peek().is_some() {
solve(&mut input, &mut output, i, &mut pre_calc);
i += 1;
}
}
}
output.flush();
match TASK_TYPE {
TaskType::Classic => input.is_empty(),
TaskType::Interactive => true,
}
}
fn main() {
let mut sin = std::io::stdin();
let input = crate::algo_lib::io::input::Input::new(&mut sin);
let mut stdout = std::io::stdout();
let output = crate::algo_lib::io::output::Output::new(&mut stdout);
run(input, output);
}
pub mod algo_lib {
pub mod collections {
pub mod vec_ext {
pub mod default {
pub fn default_vec<T: Default>(len: usize) -> Vec<T> {
let mut v = Vec::with_capacity(len);
for _ in 0..len {
v.push(T::default());
}
v
}
}
pub mod gen {
pub trait VecGen<T> {
fn gen(n: usize, f: impl FnMut(usize, &Self) -> T) -> Vec<T>;
fn gen_append(&mut self, n: usize, f: impl FnMut(usize, &Self) -> T);
fn gen_back(n: usize, f: impl FnMut(usize, &Self) -> T) -> Vec<T>
where
T: Default + Clone;
}
impl<T> VecGen<T> for Vec<T> {
fn gen(n: usize, f: impl FnMut(usize, &Self) -> T) -> Vec<T> {
let mut vec = Vec::with_capacity(n);
vec.gen_append(n, f);
vec
}
fn gen_append(&mut self, n: usize, mut f: impl FnMut(usize, &Self) -> T) {
self.reserve(n);
let len = self.len();
for i in 0..n {
self.push(f(len + i, self));
}
}
fn gen_back(n: usize, mut f: impl FnMut(usize, &Self) -> T) -> Vec<T>
where
T: Default + Clone,
{
let mut vec = vec![T::default(); n];
for i in (0..n).rev() {
vec[i] = f(i, &vec);
}
vec
}
}
}
}
}
pub mod io {
pub mod input {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::io::Read;
use std::mem::MaybeUninit;
pub struct Input<'s> {
input: &'s mut (dyn Read + Send),
buf: Vec<u8>,
at: usize,
buf_read: usize,
eol: bool,
}
macro_rules! read_impl {
($t:ty, $read_name:ident, $read_vec_name:ident) => {
pub fn $read_name (& mut self) -> $t { self.read() } pub fn $read_vec_name (& mut
self, len : usize) -> Vec <$t > { self.read_vec(len) }
};
($t:ty, $read_name:ident, $read_vec_name:ident, $read_pair_vec_name:ident) => {
read_impl!($t, $read_name, $read_vec_name); pub fn $read_pair_vec_name (& mut
self, len : usize) -> Vec < ($t, $t) > { self.read_vec(len) }
};
}
impl<'s> Input<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(input: &'s mut (dyn Read + Send)) -> Self {
Self {
input,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn new_with_size(input: &'s mut (dyn Read + Send), buf_size: usize) -> Self {
Self {
input,
buf: default_vec(buf_size),
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
if res == b'\r' {
self.eol = true;
if self.refill_buffer() && self.buf[self.at] == b'\n' {
self.at += 1;
}
return Some(b'\n');
}
self.eol = res == b'\n';
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
Some(if res == b'\r' { b'\n' } else { res })
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !b.is_ascii_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if c.is_ascii_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() { None } else { Some(res) }
}
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn is_empty(&mut self) -> bool {
self.skip_whitespace();
self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn read_vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0..size {
res.push(self.read());
}
res
}
pub fn read_char(&mut self) -> u8 {
self.skip_whitespace();
self.get().unwrap()
}
read_impl!(u32, read_unsigned, read_unsigned_vec);
read_impl!(u64, read_u64, read_u64_vec);
read_impl!(usize, read_size, read_size_vec, read_size_pair_vec);
read_impl!(i32, read_int, read_int_vec, read_int_pair_vec);
read_impl!(i64, read_long, read_long_vec, read_long_pair_vec);
read_impl!(i128, read_i128, read_i128_vec);
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
pub fn is_eol(&self) -> bool {
self.eol
}
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for u8 {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.read_vec(size)
}
}
impl<T: Readable, const SIZE: usize> Readable for [T; SIZE] {
fn read(input: &mut Input) -> Self {
unsafe {
let mut res = MaybeUninit::<[T; SIZE]>::uninit();
for i in 0..SIZE {
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(i).write(input.read::<T>());
}
res.assume_init()
}
}
}
macro_rules! read_integer {
($($t:ident)+) => {
$(impl Readable for $t { fn read(input : & mut Input) -> Self { input
.skip_whitespace(); let mut c = input.get().unwrap(); let sgn = match c { b'-' =>
{ c = input.get().unwrap(); true } b'+' => { c = input.get().unwrap(); false } _
=> false, }; let mut res = 0; loop { assert!(c.is_ascii_digit()); res *= 10; let
d = (c - b'0') as $t; if sgn { res -= d; } else { res += d; } match input.get() {
None => break, Some(ch) => { if ch.is_ascii_whitespace() { break; } else { c =
ch; } } } } res } })+
};
}
read_integer!(i8 i16 i32 i64 i128 isize u16 u32 u64 u128 usize);
macro_rules! tuple_readable {
($($name:ident)+) => {
impl <$($name : Readable),+> Readable for ($($name,)+) { fn read(input : & mut
Input) -> Self { ($($name ::read(input),)+) } }
};
}
tuple_readable! {
T
}
tuple_readable! {
T U
}
tuple_readable! {
T U V
}
tuple_readable! {
T U V X
}
tuple_readable! {
T U V X Y
}
tuple_readable! {
T U V X Y Z
}
tuple_readable! {
T U V X Y Z A
}
tuple_readable! {
T U V X Y Z A B
}
tuple_readable! {
T U V X Y Z A B C
}
tuple_readable! {
T U V X Y Z A B C D
}
tuple_readable! {
T U V X Y Z A B C D E
}
tuple_readable! {
T U V X Y Z A B C D E F
}
impl Read for Input<'_> {
fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
if self.at == self.buf_read {
self.input.read(buf)
} else {
let mut i = 0;
while i < buf.len() && self.at < self.buf_read {
buf[i] = self.buf[self.at];
i += 1;
self.at += 1;
}
Ok(i)
}
}
}
}
pub mod output {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::cmp::Reverse;
use std::io::{stderr, Stderr, Write};
#[derive(Copy, Clone)]
pub enum BoolOutput {
YesNo,
YesNoCaps,
PossibleImpossible,
Custom(&'static str, &'static str),
}
impl BoolOutput {
pub fn output(&self, output: &mut Output, val: bool) {
(if val { self.yes() } else { self.no() }).write(output);
}
fn yes(&self) -> &str {
match self {
BoolOutput::YesNo => "Yes",
BoolOutput::YesNoCaps => "YES",
BoolOutput::PossibleImpossible => "Possible",
BoolOutput::Custom(yes, _) => yes,
}
}
fn no(&self) -> &str {
match self {
BoolOutput::YesNo => "No",
BoolOutput::YesNoCaps => "NO",
BoolOutput::PossibleImpossible => "Impossible",
BoolOutput::Custom(_, no) => no,
}
}
}
pub struct Output<'s> {
output: &'s mut dyn Write,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
bool_output: BoolOutput,
precision: Option<usize>,
separator: u8,
}
impl<'s> Output<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: false,
bool_output: BoolOutput::YesNoCaps,
precision: None,
separator: b' ',
}
}
pub fn new_with_auto_flush(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: true,
bool_output: BoolOutput::YesNoCaps,
precision: None,
separator: b' ',
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.output.flush().unwrap();
self.at = 0;
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
self.maybe_flush();
}
pub fn print_line<T: Writable>(&mut self, s: T) {
self.print(s);
self.put(b'\n');
self.maybe_flush();
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
self.print_per_line_iter(arg.iter());
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(self.separator);
}
e.write(self);
}
}
pub fn print_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
self.print_iter(iter);
self.put(b'\n');
}
pub fn print_per_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
for e in iter {
e.write(self);
self.put(b'\n');
}
}
pub fn set_bool_output(&mut self, bool_output: BoolOutput) {
self.bool_output = bool_output;
}
pub fn set_precision(&mut self, precision: usize) {
self.precision = Some(precision);
}
pub fn reset_precision(&mut self) {
self.precision = None;
}
pub fn get_precision(&self) -> Option<usize> {
self.precision
}
pub fn separator(&self) -> u8 {
self.separator
}
pub fn set_separator(&mut self, separator: u8) {
self.separator = separator;
}
}
impl Write for Output<'_> {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
self.maybe_flush();
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl Writable for u8 {
fn write(&self, output: &mut Output) {
output.put(*self);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable, const N: usize> Writable for [T; N] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable + ?Sized> Writable for &T {
fn write(&self, output: &mut Output) {
T::write(self, output)
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self.as_slice().write(output);
}
}
impl Writable for () {
fn write(&self, _output: &mut Output) {}
}
macro_rules! write_to_string {
($($t:ident)+) => {
$(impl Writable for $t { fn write(& self, output : & mut Output) { self
.to_string().write(output); } })+
};
}
write_to_string!(u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
macro_rules! tuple_writable {
($name0:ident $($name:ident : $id:tt)*) => {
impl <$name0 : Writable, $($name : Writable,)*> Writable for ($name0, $($name,)*)
{ fn write(& self, out : & mut Output) { self.0.write(out); $(out.put(out
.separator); self.$id .write(out);)* } }
};
}
tuple_writable! {
T
}
tuple_writable! {
T U : 1
}
tuple_writable! {
T U : 1 V : 2
}
tuple_writable! {
T U : 1 V : 2 X : 3
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6 B : 7
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6 B : 7 C : 8
}
impl<T: Writable> Writable for Option<T> {
fn write(&self, output: &mut Output) {
match self {
None => (-1).write(output),
Some(t) => t.write(output),
}
}
}
impl Writable for bool {
fn write(&self, output: &mut Output) {
let bool_output = output.bool_output;
bool_output.output(output, *self)
}
}
impl<T: Writable> Writable for Reverse<T> {
fn write(&self, output: &mut Output) {
self.0.write(output);
}
}
static mut ERR: Option<Stderr> = None;
pub fn err() -> Output<'static> {
unsafe {
if ERR.is_none() {
ERR = Some(stderr());
}
Output::new_with_auto_flush(ERR.as_mut().unwrap())
}
}
}
}
pub mod misc {
pub mod test_type {
pub enum TestType {
Single,
MultiNumber,
MultiEof,
}
pub enum TaskType {
Classic,
Interactive,
}
}
}
pub mod string {
pub mod str {
use crate::algo_lib::io::input::{Input, Readable};
use crate::algo_lib::io::output::{Output, Writable};
use std::fmt::Display;
use std::io::Write;
use std::iter::FromIterator;
use std::ops::{AddAssign, Deref, DerefMut};
use std::str::from_utf8_unchecked;
use std::vec::IntoIter;
#[derive(Eq, PartialEq, Hash, PartialOrd, Ord, Clone, Default)]
pub struct Str(Vec<u8>);
impl Str {
pub fn new() -> Self {
Self(Vec::new())
}
pub fn unwrap(self) -> Vec<u8> {
self.0
}
}
impl From<Vec<u8>> for Str {
fn from(v: Vec<u8>) -> Self {
Self(v)
}
}
impl From<&[u8]> for Str {
fn from(v: &[u8]) -> Self {
Self(v.to_vec())
}
}
impl<const N: usize> From<&[u8; N]> for Str {
fn from(v: &[u8; N]) -> Self {
Self(v.to_vec())
}
}
impl Readable for Str {
fn read(input: &mut Input) -> Self {
let mut res = Vec::new();
input.skip_whitespace();
while let Some(c) = input.get() {
if c.is_ascii_whitespace() {
break;
}
res.push(c);
}
Self(res)
}
}
impl Writable for Str {
fn write(&self, output: &mut Output) {
output.write_all(&self.0).unwrap()
}
}
impl Deref for Str {
type Target = Vec<u8>;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl DerefMut for Str {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl IntoIterator for Str {
type Item = u8;
type IntoIter = IntoIter<u8>;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
}
impl<'a> IntoIterator for &'a Str {
type Item = &'a u8;
type IntoIter = std::slice::Iter<'a, u8>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a> IntoIterator for &'a mut Str {
type Item = &'a mut u8;
type IntoIter = std::slice::IterMut<'a, u8>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl FromIterator<u8> for Str {
fn from_iter<T: IntoIterator<Item = u8>>(iter: T) -> Self {
Self(iter.into_iter().collect())
}
}
impl AsRef<[u8]> for Str {
fn as_ref(&self) -> &[u8] {
&self.0
}
}
impl AddAssign<&[u8]> for Str {
fn add_assign(&mut self, rhs: &[u8]) {
self.0.extend_from_slice(rhs)
}
}
impl Display for Str {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
unsafe { f.write_str(from_utf8_unchecked(&self.0)) }
}
}
pub trait StrReader {
fn read_str(&mut self) -> Str;
fn read_str_vec(&mut self, n: usize) -> Vec<Str>;
fn read_line(&mut self) -> Str;
fn read_line_vec(&mut self, n: usize) -> Vec<Str>;
fn read_lines(&mut self) -> Vec<Str>;
}
impl StrReader for Input<'_> {
fn read_str(&mut self) -> Str {
self.read()
}
fn read_str_vec(&mut self, n: usize) -> Vec<Str> {
self.read_vec(n)
}
fn read_line(&mut self) -> Str {
let mut res = Str::new();
while let Some(c) = self.get() {
if self.is_eol() {
break;
}
res.push(c);
}
res
}
fn read_line_vec(&mut self, n: usize) -> Vec<Str> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.read_line());
}
res
}
fn read_lines(&mut self) -> Vec<Str> {
let mut res = Vec::new();
while !self.is_exhausted() {
res.push(self.read_line());
}
if let Some(s) = res.last() {
if s.is_empty() {
res.pop();
}
}
res
}
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 2136kb
input:
2 RRLLRRLL 4 LLLLL LLR LRLR R RLLLLLL 3 LLLLL RL RRL
output:
NO YES NO YES YES YES NO
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 25ms
memory: 2232kb
input:
100000 RRLLR 4 R R R R LRLLL 6 R L L L L R RLLRR 1 L LRLLL 3 R L L RLRRL 2 LRRRR RRRL LRLRR 2 L R RRLRL 4 RLRLR RLLL LR RLL RLRLL 8 R R R L L L R L RLLRR 7 R LL RL R L L L LLRLR 2 L R RRRRL 1 RLLLR RRLLL 2 L L RLLRL 1 RLLRL LRLLL 5 RLRLL RLLLR RRRRL LLRRR RLLRR LRLLL 3 RRLL R RL LLRRL 3 L R LLLRR RR...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO NO NO NO NO NO YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES N...
result:
wrong answer 5th lines differ - expected: 'NO', found: 'YES'