Task: | Pyramidi |
Sender: | Hennkka |
Submission time: | 2020-11-27 20:26:35 +0200 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 17 |
#2 | ACCEPTED | 83 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2 | details |
#2 | ACCEPTED | 0.01 s | 1, 2 | details |
#3 | ACCEPTED | 0.01 s | 1, 2 | details |
#4 | ACCEPTED | 0.01 s | 1, 2 | details |
#5 | ACCEPTED | 0.01 s | 1, 2 | details |
#6 | ACCEPTED | 0.01 s | 1, 2 | details |
#7 | ACCEPTED | 0.01 s | 1, 2 | details |
#8 | ACCEPTED | 0.01 s | 1, 2 | details |
#9 | ACCEPTED | 0.01 s | 1, 2 | details |
#10 | ACCEPTED | 0.01 s | 1, 2 | details |
#11 | ACCEPTED | 0.01 s | 1, 2 | details |
#12 | ACCEPTED | 0.01 s | 1, 2 | details |
#13 | ACCEPTED | 0.01 s | 1, 2 | details |
#14 | ACCEPTED | 0.01 s | 1, 2 | details |
#15 | ACCEPTED | 0.01 s | 1, 2 | details |
#16 | ACCEPTED | 0.03 s | 2 | details |
#17 | ACCEPTED | 0.03 s | 2 | details |
#18 | ACCEPTED | 0.03 s | 2 | details |
#19 | ACCEPTED | 0.03 s | 2 | details |
#20 | ACCEPTED | 0.03 s | 2 | details |
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 |