CSES - Putka Open 2020 – 5/5 - Results
Submission details
Task:Pyramidi
Sender:Hennkka
Submission time:2020-11-27 20:26:35 +0200
Language:Rust
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED17
#2ACCEPTED83
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s1, 2details
#3ACCEPTED0.01 s1, 2details
#4ACCEPTED0.01 s1, 2details
#5ACCEPTED0.01 s1, 2details
#6ACCEPTED0.01 s1, 2details
#7ACCEPTED0.01 s1, 2details
#8ACCEPTED0.01 s1, 2details
#9ACCEPTED0.01 s1, 2details
#10ACCEPTED0.01 s1, 2details
#11ACCEPTED0.01 s1, 2details
#12ACCEPTED0.01 s1, 2details
#13ACCEPTED0.01 s1, 2details
#14ACCEPTED0.01 s1, 2details
#15ACCEPTED0.01 s1, 2details
#16ACCEPTED0.03 s2details
#17ACCEPTED0.03 s2details
#18ACCEPTED0.03 s2details
#19ACCEPTED0.03 s2details
#20ACCEPTED0.03 s2details

Code

use std::io::BufRead;

const MAX_N: usize = 1_000_000;

/// The number of 2's in the factorial of 2
fn factorial_2(n: usize) -> usize {
    thread_local! {
        static MEM: Vec<usize> = (0..=MAX_N)
            .into_iter()
            .map(|v| if v > 0 {v.trailing_zeros() as usize} else {0})
            .scan(0usize, |s, v| {
                *s += v;
                Some(*s)
            })
            .collect();
    }

    MEM.with(|mem| mem[n])
}

fn binomial_parity(n: usize, k: usize) -> bool {
    factorial_2(n) - factorial_2(k) - factorial_2(n - k) > 0
}

fn sierpinski_row(n: usize) -> Vec<bool> {
    (0..n).map(|v| !binomial_parity(n - 1, v)).collect()
}

fn solve(row: Vec<usize>) -> usize {
    let n = row.len();
    row.into_iter()
        .zip(sierpinski_row(n).into_iter())
        .filter(|(_, b)| *b)
        .map(|(v, _)| v)
        .fold(0, |a, b| a ^ b)
}

fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();

    let _n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let input: Vec<usize> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|v| v.parse().unwrap())
        .collect();
    println!("{}", solve(input));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sample() {
        assert_eq!(solve(vec![2, 10, 5, 12, 9, 5, 1, 5]), 9);
    }
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
1
80

correct output
80

user output
80

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
2
69 91

correct output
30

user output
30

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
3
47 74 75

correct output
100

user output
100

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
4
94 22 100 43

correct output
7

user output
7

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
5
50 82 47 40 51

correct output
1

user output
1

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
6
90 27 98 85 47 14

correct output
96

user output
96

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
7
55 82 52 9 65 90 86

correct output
20

user output
20

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
8
45 52 52 95 40 85 3 46

correct output
34

user output
34

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
9
77 16 59 32 22 41 87 89 78

correct output
3

user output
3

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
10
59 78 34 26 71 9 82 68 80 74

correct output
111

user output
111

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
100
100 6 10 53 84 80 7 87 3 82 26...

correct output
91

user output
91

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
100
25 18 62 51 79 55 71 33 21 29 ...

correct output
58

user output
58

Test 13

Group: 1, 2

Verdict: ACCEPTED

input
100
3 20 19 60 11 84 94 79 63 59 9...

correct output
124

user output
124

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
100
99 86 42 2 97 78 8 12 98 7 98 ...

correct output
49

user output
49

Test 15

Group: 1, 2

Verdict: ACCEPTED

input
100
19 19 14 30 80 53 21 18 26 85 ...

correct output
42

user output
42

Test 16

Group: 2

Verdict: ACCEPTED

input
200000
852837035 608724072 368935143 ...

correct output
680579671

user output
680579671

Test 17

Group: 2

Verdict: ACCEPTED

input
200000
255817977 550740070 115276527 ...

correct output
177586289

user output
177586289

Test 18

Group: 2

Verdict: ACCEPTED

input
200000
30889540 9467827 526159961 367...

correct output
439343644

user output
439343644

Test 19

Group: 2

Verdict: ACCEPTED

input
200000
421000302 598694653 199802169 ...

correct output
184880259

user output
184880259

Test 20

Group: 2

Verdict: ACCEPTED

input
200000
578873143 289492857 855880936 ...

correct output
937457144

user output
937457144