Lista

warning: unused imports: `Hash`, `Hasher`
 --> input/code.rs:3:17
  |
3 | use std::hash::{Hash, Hasher};
  |                 ^^^^  ^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::hash_map::DefaultHasher`
 --> input/code.rs:4:5
  |
4 | use std::collections::hash_map::DefaultHasher;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

use std::io;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;


fn rec_find(
    known_invalids: &mut HashMap<u64, bool>,
    pairs: &Vec<(u32, u32)>,
    pairs_by_first: &HashMap<u32, Vec<(u32, u32)>>,
    remaining_depth: u32,
    last_choice: Option<(u32, u32)>,
    solution: &mut Vec<u32>,
    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 mut hash = DefaultHasher::new();
            // solution.hash(&mut hash);
            // choice.hash(&mut hash);
            // let hash_value: u64 = hash.finish();

            // let mut hash2 = DefaultHasher::new();
            // solution.hash(&mut hash2);
            // choice.hash(&mut hash2);
            // let hash_value2: u64 = hash.finish();
            // if hash_value != hash_value2 {
            //     println!("HMMMM")
            // }

            // if known_invalids.contains_key(&hash_value) {
            //     // println!("HMM")
            // } else {
            let ret_val = rec_find(
                known_invalids,
                pairs,
                pairs_by_first,
                remaining_depth - 1,
                Some(*choice),
                solution,
                solution_hash,
                primes,
            );
            match ret_val {
                Some(v) => { return Some(v); }
                None => {}
            }
            // }
            //
            // known_invalids.insert(hash_value, true);

            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);
    }

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

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 3

Verdict: ACCEPTED