CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Lista
Sender:osku91
Submission time:2020-09-06 21:21:14 +0300
Language:Rust
Status:READY
Result:59
Feedback
groupverdictscore
#1ACCEPTED21
#2ACCEPTED38
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.01 s2, 3details
#14ACCEPTED0.01 s2, 3details
#15ACCEPTED0.01 s2, 3details
#16--3details
#17ACCEPTED0.09 s3details
#18--3details
#19--3details
#20--3details
#21ACCEPTED0.04 s3details

Compiler report

warning: variable does not need to be mutable
  --> input/code.rs:10:5
   |
10 |     mut solution: &mut Vec<u32>,
   |     ----^^^^^^^^
   |     |
   |     help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
  --> input/code.rs:11:5
   |
11 |     mut solution_hash: &mut HashMap<u32, bool>,
   |     ----^^^^^^^^^^^^^
   |     |
   |     help: remove this `mut`

Code

use std::io;
use std::collections::HashMap;


fn rec_find(
    pairs: &Vec<(u32, u32)>,
    pairs_by_first: &HashMap<u32, Vec<(u32, u32)>>,
    remaining_depth: u32,
    last_choice: Option<(u32, u32)>,
    mut solution: &mut Vec<u32>,
    mut solution_hash: &mut HashMap<u32, bool>,
    primes: &HashMap<u32, bool>,
) -> Option<Vec<u32>> {
    let mut iterator = pairs;
    match last_choice {
        Some(c) => {
            iterator = &pairs_by_first[&c.1]
        },
        None => {}
    }

    for choice in iterator {
        match last_choice {
            Some(c) => {
                if c.1 != choice.0 {
                    continue
                }
            },
            None  => {

            }
        }
        if solution_hash.contains_key(&choice.0) {
            continue
        }
        if solution_hash.contains_key(&choice.1) {
            continue
        }

        if remaining_depth == 2 {
            if primes.contains_key(&(choice.0 + choice.1)) {
                solution.push(choice.0);
                solution.push(choice.1);
                return Some(solution.clone());
            }
        } else {
            solution.push(choice.0);
            solution_hash.insert(choice.0, true);
            let ret_val = rec_find(
                pairs,
                pairs_by_first,
                remaining_depth - 1,
                Some(*choice),
                solution,
                solution_hash,
                primes,
            );
            match ret_val {
                Some(v) => {return Some(v)}
                None => {}
            }
            solution_hash.remove(&choice.0);
            solution.pop();
        }
    }
    return None
}


fn main() {
    let mut input_text = String::new();
    io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");

    let trimmed = input_text.trim();

    let n: u32 = trimmed.parse::<u32>().unwrap();
    // println!("asdf");

    // let n: u32 = 7;

    let mut primes: HashMap<u32, bool> = HashMap::new();
    for i in 2..(n * 2 + 5) {
        let mut is_prime: bool = true;

        for (prime, _) in &primes {
            if i % prime == 0 {
                is_prime = false;
                break;
            }
        }

        if is_prime {
            primes.insert(i, true);
        }
    }

    let mut pairs: Vec<(u32, u32)> = vec![];
    let mut pairs_by_first: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
    for i in 1..n+1 {
        let mut pairs_in_first: Vec<(u32, u32)> = vec![];
        for j in 1..n+1 {
            if i != j && primes.contains_key(&(i + j)) {
                pairs.push((i, j));
                pairs_in_first.push((i, j));
            }
        }
        pairs_by_first.insert(i, pairs_in_first);
    }

    // println!("n is {}", n);
    // println!("primes {:#?}", primes);

    let mut solution: Vec<u32> = vec![];
    let mut solution_hash: HashMap<u32, bool> = HashMap::new();
    match rec_find(
        &pairs,
        &pairs_by_first,
        n,
        None,
        &mut solution,
        &mut solution_hash,
        &primes,
    ) {
        Some(value) => {
            for i in value {
                print!("{} ", i)
            }
            println!("")
            // println!("FOUND {:#?}", value)
        },
        None => {println!("Not found")}
    };
    // println!("pairs {:#?}", pairs);
    // println!("pairs {:#?}", pairs_by_first);
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
2

correct output
1 2 

user output
1 2 

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
3

correct output
1 2 3 

user output
1 2 3 

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
1 2 3 4 

user output
1 2 3 4 

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
3 4 1 2 5 

user output
1 4 3 2 5 

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
3 4 1 2 5 6 

user output
1 4 3 2 5 6 

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
3 4 1 2 5 6 7 

user output
1 2 3 4 7 6 5 

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
7 6 5 2 1 4 3 8 

user output
1 2 3 4 7 6 5 8 

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
7 6 5 2 1 4 3 8 9 

user output
1 2 3 4 7 6 5 8 9 

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

correct output
7 6 5 2 1 4 3 8 9 10 

user output
1 2 3 4 7 6 5 8 9 10 

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
19

correct output
17 14 3 8 15 16 13 6 5 2 1 4 9...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
56

correct output
55 54 53 50 51 52 49 48 13 28 ...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
70

correct output
67 4 1 2 9 32 35 38 65 66 61 4...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
76

correct output
73 66 61 42 59 54 53 50 51 52 ...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
90

correct output
87 86 11 18 29 44 45 16 55 58 ...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
100

correct output
97 96 95 78 25 82 81 56 71 68 ...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 16

Group: 3

Verdict:

input
154

correct output
151 6 5 92 137 134 149 84 143 ...

user output
(empty)

Test 17

Group: 3

Verdict: ACCEPTED

input
430

correct output
427 426 371 372 367 376 375 35...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

Test 18

Group: 3

Verdict:

input
629

correct output
627 404 227 146 83 150 77 74 3...

user output
(empty)

Test 19

Group: 3

Verdict:

input
833

correct output
829 828 793 574 523 516 515 51...

user output
(empty)

Test 20

Group: 3

Verdict:

input
885

correct output
883 724 723 878 881 726 721 71...

user output
(empty)

Test 21

Group: 3

Verdict: ACCEPTED

input
1000

correct output
997 996 737 884 995 492 991 20...

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...