Monistus

use std::{char, io::*};
 
const MAX_CAPACITY: usize = 600000;
const CUTOFF_CHUNK_SIZE: i32 = 30;
 
#[derive(Copy, Clone, Debug)]
enum Char {
    Letter(char),
    Digit(u8),
    Unused,
}
 
fn print_buffer(buffer: &[Char]) {
    for c in buffer {
        match c {
            Char::Digit(digit) => {
                print!("\x1b[93m{digit}\x1b[0m")
            }
            Char::Letter(l) => {
                print!("{l}")
            }
            Char::Unused => {}
        }
    }
    println!("");
}
 
fn main() -> Result<()> {
    let mut input = String::new();
    stdin().read_line(&mut input)?;
 
    let mapped_input = input
        .chars()
        .map(|char| {
            if let Ok(digit) = char.to_string().parse::<u8>() {
                Char::Digit(digit)
            } else {
                Char::Letter(char)
            }
        })
        .collect::<Vec<_>>();
 
    let mut buffer = [Char::Unused; MAX_CAPACITY];
    let input_slice = mapped_input.as_slice();
    buffer[..input.len()].copy_from_slice(input_slice);
 
    let mut i = 0;
    let mut last = input.len();
    let mut cutoff = 1.max(input_slice.len() as i32 - CUTOFF_CHUNK_SIZE);
 
    loop {
        match buffer[i] {
            Char::Digit(digit) => {
                let digit = digit as usize;
                //println!("\nIndex: {}", i);
                //println!("Copies:");
 
                if i + CUTOFF_CHUNK_SIZE as usize > last - cutoff as usize {
                    let new_cutoff = 1.max(cutoff - CUTOFF_CHUNK_SIZE);
                    buffer[(last - cutoff as usize)..(last - new_cutoff as usize)].copy_from_slice(
                        &input_slice[(input_slice.len() - cutoff as usize)
                            ..(input_slice.len() - new_cutoff as usize)],
                    );
                    cutoff = new_cutoff;
                }
 
                if i + 1 + digit < last {
                    buffer.copy_within((i + 1 + digit)..(last - cutoff as usize), i + 2 * digit);
                }
                //print_buffer(&buffer);
 
                buffer.copy_within((i + 1)..(i + 1 + digit), i + digit);
                //print_buffer(&buffer);
 
                buffer.copy_within((i + digit)..(i + 2 * digit), i);
                //print_buffer(&buffer);
 
                last = last
                    .max(i + 2 * digit + (last - (i + 1 + digit)))
                    .max(i + digit + ((i + 1 + digit) - (i + 1)))
                    .max(i + ((i + 2 * digit) - (i + digit)));
            }
            Char::Letter(_) => {
                i += 1;
            }
            Char::Unused => break,
        }
    }
    //println!("\nResult:");
    print_buffer(&buffer);
    Ok(())
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED