CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Lista
Sender:osku91
Submission time:2020-09-06 22:40:23 +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: 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;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Code

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 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 ...
Truncated

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 ...
Truncated

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 ...
Truncated

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 ...
Truncated

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 ...
Truncated

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 ...
Truncated

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 ...
Truncated