Task: | Key cutting |
Sender: | Viestipojat |
Submission time: | 2024-11-16 13:28:05 +0200 |
Language: | Rust (2021) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.01 s | details |
#10 | ACCEPTED | 0.01 s | details |
#11 | ACCEPTED | 0.01 s | details |
#12 | ACCEPTED | 0.01 s | details |
#13 | ACCEPTED | 0.02 s | details |
#14 | ACCEPTED | 0.02 s | details |
Code
use std::str::FromStr; use std::fmt::Debug; fn read<T: FromStr>() -> Vec<T> where <T as FromStr>::Err: Debug { let stdin = std::io::stdin(); let line = stdin.lines().next().unwrap().unwrap(); line.split_whitespace().map(T::from_str).map(|x| x.unwrap()).collect() } fn main() { let _n = read::<usize>()[0]; let mut hs = read::<u32>(); hs.dedup(); let mut ll = hs.iter().enumerate().map(|(i, h)| (*h, i.wrapping_sub(1), i + 1, true)).collect::<Vec<_>>(); let mut steps = 0; let mut q = hs.into_iter().enumerate().collect::<Vec<_>>(); q.sort_by_key(|(_i, h)| *h); while let Some((i, h)) = q.pop() { if h == 0 { break; } let (_h, p, n, a) = ll[i]; if a { ll[i].3 = false; steps += 1; let Some((hp, _pp, _np, _)) = ll.get(p) else { if ll.get(n).is_some() { ll[n].1 = usize::MAX; } continue; }; let Some((hn, _pn, _nn, _)) = ll.get(n) else { if ll.get(p).is_some() { ll[p].2 = usize::MAX; } continue; }; if hp == hn { ll[n].3 = false; let nn = ll[n].2; if ll.get(nn).is_some() { ll[p].2 = nn; ll[nn].1 = p; } else { ll[p].2 = usize::MAX; } } else { ll[p].2 = n; ll[n].1 = p; } } } println!("{steps}"); }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
3 1 2 1 |
correct output |
---|
2 |
user output |
---|
2 |
Test 2
Verdict: ACCEPTED
input |
---|
1 0 |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Verdict: ACCEPTED
input |
---|
1 9 |
correct output |
---|
1 |
user output |
---|
1 |
Test 4
Verdict: ACCEPTED
input |
---|
100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 5
Verdict: ACCEPTED
input |
---|
100 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 ... |
correct output |
---|
25 |
user output |
---|
25 |
Test 6
Verdict: ACCEPTED
input |
---|
100 2 1 2 1 2 0 0 0 1 1 2 2 1 2 2 ... |
correct output |
---|
41 |
user output |
---|
41 |
Test 7
Verdict: ACCEPTED
input |
---|
100 36 5 10 37 94 59 20 31 64 2 58... |
correct output |
---|
99 |
user output |
---|
99 |
Test 8
Verdict: ACCEPTED
input |
---|
100 228768416 32415139 952687252 6... |
correct output |
---|
100 |
user output |
---|
100 |
Test 9
Verdict: ACCEPTED
input |
---|
100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 10
Verdict: ACCEPTED
input |
---|
100000 1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 ... |
correct output |
---|
24965 |
user output |
---|
24965 |
Test 11
Verdict: ACCEPTED
input |
---|
100000 2 1 2 2 2 2 2 1 1 0 1 1 0 1 1 ... |
correct output |
---|
38968 |
user output |
---|
38968 |
Test 12
Verdict: ACCEPTED
input |
---|
100000 4 4 5 4 4 5 0 2 2 1 4 4 1 0 5 ... |
correct output |
---|
59156 |
user output |
---|
59156 |
Test 13
Verdict: ACCEPTED
input |
---|
100000 18 5 6 16 8 10 1 7 4 15 5 9 19... |
correct output |
---|
82598 |
user output |
---|
82598 |
Test 14
Verdict: ACCEPTED
input |
---|
100000 33 37 37 86 42 38 18 10 77 57 ... |
correct output |
---|
94897 |
user output |
---|
94897 |