QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#804152#9873. Last Chance: Threads of Despairucup-team296#WA 0ms2224kbRust18.4kb2024-12-07 20:40:372024-12-07 20:40:38

Judging History

你现在查看的是最新测评结果

  • [2024-12-07 20:40:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:2224kb
  • [2024-12-07 20:40:37]
  • 提交

answer

// https://contest.ucup.ac/contest/1871/problem/9873
pub mod solution {
//{"name":"L. Last Chance: Threads of Despair","group":"Universal Cup - The 3rd Universal Cup. Stage 20: Kunming","url":"https://contest.ucup.ac/contest/1871/problem/9873","interactive":false,"timeLimit":1000,"tests":[{"input":"3\n3 2\n1 1 4\n2 6\n3 2\n1 1 4\n2 7\n2 1\n100 100\n2\n","output":"Yes\nNo\nYes\n"},{"input":"3\n7 1\n1 1 1 1 1 1 1\n9\n5 2\n3 4 5 6 7\n1 6\n5 3\n3 4 5 6 7\n1 5 7\n","output":"No\nNo\nYes\n"}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"LLastChanceThreadsOfDespair"}}}

use crate::algo_lib::collections::vec_ext::sorted::Sorted;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::BoolOutput;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::misc::test_type::TaskType;

use crate::algo_lib::misc::test_type::TestType;

type PreCalc = ();

fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &mut PreCalc) {
    let n = input.read_size();
    let m = input.read_size();
    let mut h0 = input.read_size_vec(n).sorted();
    let mut h1 = input.read_size_vec(m).sorted();

    let mut level = 0;
    let mut shots = 0;
    let mut j = 0;
    let mut k = 0;
    for i in 0..n {
        if h0[i] > level {
            h0[i] -= 1;
            shots += 1;
        }
        loop {
            if j < m && h1[j] <= level {
                j += 1;
                level += 1;
            } else if k < n && h0[k] <= level {
                k += 1;
                level += 1;
            } else {
                break;
            }
        }
    }
    while j < m {
        if shots == 0 {
            out.print_line(false);
            return;
        }
        h1[j] -= 1;
        shots -= 1;
        loop {
            if j < m && h1[j] <= level {
                j += 1;
                level += 1;
            } else if k < n && h0[k] <= level {
                k += 1;
                level += 1;
            } else {
                break;
            }
        }
    }
    out.print_line(true);
}

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 = ();
    output.set_bool_output(BoolOutput::YesNo);

    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,
    }
}

}
pub mod algo_lib {
#![allow(clippy::too_many_arguments)]
#![allow(clippy::type_complexity)]
#![allow(clippy::missing_safety_doc)]
#![allow(clippy::legacy_numeric_constants)]

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 sorted {
pub trait Sorted {
    fn sorted(self) -> Self;
}

impl<T: Ord> Sorted for Vec<T> {
    fn sorted(mut self) -> Self {
        self.sort();
        self
    }
}
}
}
}
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,
}

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,
        }
    }

    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,
        }
    }

    pub fn get(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            let res = self.buf[self.at];
            self.at += 1;
            if res == b'\r' {
                if self.refill_buffer() && self.buf[self.at] == b'\n' {
                    self.at += 1;
                }
                return Some(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)
        }
    }

    //noinspection RsSelfConvention
    pub fn is_exhausted(&mut self) -> bool {
        self.peek().is_none()
    }

    //noinspection RsSelfConvention
    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 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;
use std::io::Stderr;
use std::io::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>,
}

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,
        }
    }

    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,
        }
    }

    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(b' ');
            }
            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
    }
}

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(b' ');
                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,
}
}
}
}
fn main() {
    let mut sin = std::io::stdin();
    let input = algo_lib::io::input::Input::new(&mut sin);
    let mut stdout = std::io::stdout();
    let output = algo_lib::io::output::Output::new(&mut stdout);
    solution::run(input, output);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 2144kb

input:

3
3 2
1 1 4
2 6
3 2
1 1 4
2 7
2 1
100 100
2

output:

Yes
No
Yes

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: 0
Accepted
time: 0ms
memory: 2076kb

input:

3
7 1
1 1 1 1 1 1 1
9
5 2
3 4 5 6 7
1 6
5 3
3 4 5 6 7
1 5 7

output:

No
No
Yes

result:

ok 3 token(s): yes count is 1, no count is 2

Test #3:

score: 0
Accepted
time: 0ms
memory: 2224kb

input:

4
1 1
1
1
1 1
1
2
1 1
2
1
1 1
2
2

output:

Yes
Yes
Yes
No

result:

ok 4 token(s): yes count is 3, no count is 1

Test #4:

score: 0
Accepted
time: 0ms
memory: 2160kb

input:

18
1 2
1
1 1
1 2
1
2 1
1 2
1
1 3
1 2
1
2 2
1 2
1
3 2
1 2
1
3 3
1 2
2
1 1
1 2
2
1 2
1 2
2
1 3
1 2
2
2 2
1 2
2
2 3
1 2
2
3 3
1 2
3
1 1
1 2
3
1 2
1 2
3
1 3
1 2
3
2 2
1 2
3
3 2
1 2
3
3 3

output:

Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No

result:

ok 18 token(s): yes count is 7, no count is 11

Test #5:

score: 0
Accepted
time: 0ms
memory: 2108kb

input:

18
2 1
1 1
1
2 1
1 1
2
2 1
1 1
3
2 1
1 2
1
2 1
2 1
2
2 1
2 1
3
2 1
1 3
1
2 1
1 3
2
2 1
3 1
3
2 1
2 2
1
2 1
2 2
2
2 1
2 2
3
2 1
2 3
1
2 1
3 2
2
2 1
2 3
3
2 1
3 3
1
2 1
3 3
2
2 1
3 3
3

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No

result:

ok 18 token(s): yes count is 15, no count is 3

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 2108kb

input:

525
2 3
1 1
1 1 1
2 3
1 1
1 2 1
2 3
1 1
1 3 1
2 3
1 1
1 4 1
2 3
1 1
5 1 1
2 3
1 1
2 2 1
2 3
1 1
3 1 2
2 3
1 1
1 2 4
2 3
1 1
2 1 5
2 3
1 1
3 3 1
2 3
1 1
4 3 1
2 3
1 1
3 5 1
2 3
1 1
4 4 1
2 3
1 1
4 5 1
2 3
1 1
1 5 5
2 3
1 1
2 2 2
2 3
1 1
2 3 2
2 3
1 1
2 2 4
2 3
1 1
2 5 2
2 3
1 1
3 2 3
2 3
1 1
3 2 4
2 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Y...

result:

wrong answer expected YES, found NO [49th token]