CSES - Datatähti 2021 loppu - Results
Submission details
Task:Järjestäminen
Sender:xnor
Submission time:2021-01-23 17:26:12 +0200
Language:Rust
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED36
#2ACCEPTED64
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.01 s1, 2details

Code

use std::io::{self, BufRead};

fn main() {
    let mut lines = io::BufReader::new(io::stdin()).lines();

    let t = lines.next().unwrap().unwrap().parse::<usize>().unwrap();

    let mut arrays: Vec<Vec<usize>> = Vec::new();

    for _ in 0..t {
        let _n = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
        let array_line = lines.next().unwrap().unwrap();
        arrays.push(array_line.split_ascii_whitespace().map(|s| s.parse::<usize>().unwrap()).collect());
    }

    for array in &mut arrays {
        if try_sort(1, array) {
            println!("YES");
        } else {
            println!("NO");
        }
    }
}

fn try_sort(m: usize, array: &mut [usize]) -> bool {
    if array.len() == 1 {
        return true
    }
    if array.len() == 2 {
        return array[0] < array[1]
    }
    if array.len() == 3 {
        return array[0] < array[1] && array[1] < array[2]
    }

    if array.len() == 4 {
        if array[0] < array[1] && array[1] < array[2] && array[2] < array[3] {
            return true;
        }
        if array == &[m+2,m+3,m,m+1] {
            return true;
        }
        if m > 1 {
            return match (array[0] - m, array[1] - m, array[2] - m, array[3] - m) {
                (0, 1, 2, 3) => true,
                (0, 2, 3, 1) => true,
                (0, 3, 1, 2) => true,
                (0, 1, 3, 2) => false,
                (0, 2, 1, 3) => false,
                (0, 3, 2, 1) => false,

                (1, 0, 2, 3) => false,
                (1, 2, 3, 0) => false,
                (1, 3, 0, 2) => false,
                (1, 0, 3, 2) => true,
                (1, 2, 0, 3) => true,
                (1, 3, 2, 0) => true,

                (2, 0, 1, 3) => true,
                (2, 1, 3, 0) => true,
                (2, 3, 0, 1) => true,
                (2, 0, 3, 1) => false,
                (2, 1, 0, 3) => false,
                (2, 3, 1, 0) => false,

                (3, 0, 1, 2) => false,
                (3, 1, 2, 0) => false,
                (3, 2, 0, 1) => false,
                (3, 0, 2, 1) => true,
                (3, 1, 0, 2) => true,
                (3, 2, 1, 0) => true,
                _ => false,
            }
        }  else {
            return false;
        }

    }

    if Some(&m) == array.iter().nth(1) {
        if array.len() == 4 {
            return false;
        }

        let tmp1 = array[0];
        let tmp2 = array[1];

        array[0] = array[2];
        array[1] = array[3];
        
        array[2] = tmp1;
        array[3] = tmp2;

        return try_sort(m, array);
    }

    if Some(&m) == array.last() {
        if array.len() == 4 {
            return false;
        }
        let i = array.len() - 2;

        let tmp1 = array[1];
        let tmp2 = array[2];

        array[1] = array[i];
        array[2] = array[i+1];
        
        array[i] = tmp1;
        array[i+1] = tmp2;

        return try_sort(m, array);
    }

    if m == array[0] {
        return try_sort(m + 1, &mut array[1..])
    } else {
        let i = array.iter().position(|x| *x == m).unwrap();

        let tmp1 = array[0];
        let tmp2 = array[1];

        array[0] = array[i];
        array[1] = array[i+1];
        
        array[i] = tmp1;
        array[i+1] = tmp2;

        return try_sort(m + 1, &mut array[1..])
    }
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
153
1
1
2
1 2
...

correct output
YES
YES
NO
NO
NO
...

user output
YES
YES
NO
NO
NO
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
59
35 29 32 50 11 15 9 21 19 45 2...

correct output
YES
NO
YES
NO
YES
...

user output
YES
NO
YES
NO
YES
...
Truncated

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
720
6
1 6 4 5 2 3
6
6 3 2 1 5 4
...

correct output
YES
NO
NO
NO
YES
...

user output
YES
NO
NO
NO
YES
...
Truncated

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
1000
8
7 4 2 8 6 3 5 1
8
3 8 2 7 5 4 6 1
...

correct output
NO
NO
YES
NO
YES
...

user output
NO
NO
YES
NO
YES
...
Truncated