CSES - Datatähti 2020 loppu - Results
Submission details
Task:Riippuliito
Sender:Aleksi Hannula
Submission time:2020-02-09 16:18:42 +0200
Language:Rust
Status:READY
Result:39
Feedback
groupverdictscore
#1ACCEPTED18
#2ACCEPTED21
#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 s2, 3details
#9ACCEPTED0.02 s2, 3details
#10ACCEPTED0.02 s2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.01 s2, 3details
#14ACCEPTED0.02 s2, 3details
#15ACCEPTED0.02 s3details
#16--3details
#17--3details
#18ACCEPTED0.03 s3details
#19ACCEPTED0.04 s3details
#20--3details
#21--3details
#22ACCEPTED0.01 s1, 2, 3details
#23ACCEPTED0.01 s1, 2, 3details
#24ACCEPTED0.01 s1, 2, 3details
#25ACCEPTED0.01 s1, 2, 3details
#26ACCEPTED0.01 s1, 2, 3details
#27ACCEPTED0.01 s1, 2, 3details
#28ACCEPTED0.01 s1, 2, 3details
#29ACCEPTED0.01 s1, 2, 3details

Code

#[derive(Clone, Copy, Debug)]
struct HuippuData(Option<usize>, Option<usize>);

// Jokaiselta huipulta voi liitaa kahteen suuntaan (ikaan kuin binaaripuu), ja se suunta, jossa on enemman vuoria, on parempi

/*struct Huippu {
    korkeus: usize,
    vasen: Option<Rc<Huippu>>,
    oikea: Option<Rc<Huippu>>,
}

fn korkein_mahd_huippu(kanta: &Huippu, max_korkeus: usize) -> Option<Rc<Huippu>> {
    let vasen_max = match &kanta.vasen {
        None => None,
        Some(vasen) => {
            if vasen.korkeus < max_korkeus {
                Some(kanta.vasen.as_ref().clone())
            } else {
                korkein_mahd_huippu(&vasen, max_korkeus)
            }
        }
    };

    let oikea_max = match &kanta.oikea {
        None => None,
        Some(oikea) => {
            if oikea.korkeus < max_korkeus {
                Some(kanta.oikea.as_ref().clone())
            } else {
                korkein_mahd_huippu(&oikea, max_korkeus)
            }
        }
    };

    match oikea_max {
        None => vasen_max,
        Some(oikea) => match vasen_max {
            None => Some(oikea),
            Some(vasen) => {
                if vasen.korkeus > oikea.korkeus {
                    return Some(vasen);
                }
                Some(oikea)
            },
        }
    }
}

fn lisaa_huippu_jalkeen(kanta: &mut Huippu, uusi: Huippu) {
    let nyt_kanta = kanta;
    while kanta.oikea.is_some() {
        nyt_kanta = &mut nyt_kanta.oikea.unwrap();
    }

    uusi.vasen = match kanta.oikea {
        Some(oikea) => korkein_mahd_huippu(&oikea, kanta.korkeus),
        None => None,
    };

    kanta.oikea = Some(Rc::new(uusi));
}*/

fn tee_hyppy(huippudata: &mut [HuippuData], korkeudet: &[usize], osoitin: usize, pituus: usize) -> usize {
    if korkeudet.len() == 0 {
        return pituus;
    }

    let huippu_kork = korkeudet.iter().enumerate().fold((0, 0), |acc, x| {
        if *x.1 > acc.1 {
            return (x.0, *x.1);
        }
        return acc;
    }).1;

    let mut korkein_hyppy = 0;
    let mahd_hypyt = korkeudet.rsplit(|&x| x == huippu_kork).collect::<Vec<_>>();
    if mahd_hypyt.len() < 2 {
        return pituus;
    }

    for mahd_vuoret in mahd_hypyt {
        korkein_hyppy = std::cmp::max(korkein_hyppy, tee_hyppy(huippudata, mahd_vuoret, osoitin, pituus + 1));
    }

    return korkein_hyppy;
}

fn main() {
    let mut lkm_str = String::new();
    std::io::stdin().read_line(&mut lkm_str).unwrap();
    let lkm = lkm_str.trim().parse::<usize>().unwrap();

    let mut korkeudet_str = String::new();
    std::io::stdin().read_line(&mut korkeudet_str).unwrap();
    /*for kork in korkeudet_str.split_whitespace() {
        let korkeus = kork.trim().parse::<usize>().unwrap();
        
        // uusi korkein huippu
        if korkeus > nyk_huippu.korkeus {
            let o_nyk_huippu = nyk_huippu;
            nyk_huippu = Huippu{
                korkeus,
                vasen: Some(Rc::new(o_nyk_huippu)),
                oikea: None,
            };
        } else {
            lisaa_huippu_jalkeen(&mut nyk_huippu, Huippu{korkeus, vasen: None, oikea: None});
        }
    }*/
    let mut huippudata = std::iter::repeat(HuippuData(None, None)).take(lkm).collect::<Vec<HuippuData>>();
    let korkeudet = korkeudet_str.split_whitespace().map(|x| x.trim().parse::<usize>().unwrap()).collect::<Vec<usize>>();
    //keraa_huippudata(&mut huippudata, &korkeudet, 0);
    println!("{}", tee_hyppy(&mut huippudata, &korkeudet, 0, 0));

    /*
     * // Lista "kantamasta", jonka verran huipulta voi lentää
    let mut huipulta_paasee_vas = Vec::with_capacity(lkm);
    let mut huipulta_paasee_oik = Vec::with_capacity(lkm);
    for i in 0..lkm {
        let mut max_oikealle_huiput = 1;
        for j in (i+1)..lkm {
            if korkeudet[j] >= korkeudet[i] {
                break;
            }
            max_oikealle_huiput += 1;
        }

        let mut max_vasemmalle_huiput = 1;

        if i != 0 {
            for j in (0..=(i-1)).rev() {
                if korkeudet[j] >= korkeudet[i] {
                    break;
                }
                max_vasemmalle_huiput += 1;
            }
        }

        huipulta_paasee_vas.push(max_vasemmalle_huiput);
        huipulta_paasee_oik.push(max_oikealle_huiput);
    }*/

}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1 2 3 4 5 6 7 8 9 10

correct output
10

user output
10

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
10 9 8 7 6 5 4 3 2 1

correct output
10

user output
10

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
10 9 6 10 10 3 6 7 6 5

correct output
4

user output
4

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
51 90 27 98 85 47 14 55 82 52

correct output
6

user output
6

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
9 65 90 86 45 52 52 95 40 85

correct output
5

user output
5

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
3 46 77 16 59 32 22 41 87 89

correct output
7

user output
7

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1

user output
1

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
5000

user output
5000

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
5000
5000 4999 4998 4997 4996 4995 ...

correct output
5000

user output
5000

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
5000
10 8 10 5 4 9 2 9 10 10 1 2 7 ...

correct output
9

user output
9

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
5000
655923386 310000737 281882248 ...

correct output
28

user output
28

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
5000
123456789 123456790 123456791 ...

correct output
2706

user output
2706

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
5000
123456789 123456790 123456791 ...

correct output
5000

user output
5000

Test 15

Group: 3

Verdict: ACCEPTED

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1

user output
1

Test 16

Group: 3

Verdict:

input
200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
200000

user output
(empty)

Test 17

Group: 3

Verdict:

input
200000
200000 199999 199998 199997 19...

correct output
200000

user output
(empty)

Test 18

Group: 3

Verdict: ACCEPTED

input
200000
4 7 8 3 3 10 3 4 2 6 10 8 5 8 ...

correct output
10

user output
10

Test 19

Group: 3

Verdict: ACCEPTED

input
200000
824527039 112439661 517794857 ...

correct output
43

user output
43

Test 20

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
30764

user output
(empty)

Test 21

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
61367

user output
(empty)

Test 22

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
1

correct output
1

user output
1

Test 23

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 1

correct output
1

user output
1

Test 24

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 2

correct output
2

user output
2

Test 25

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
2 1

correct output
2

user output
2

Test 26

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 1

correct output
2

user output
2

Test 27

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 3

correct output
3

user output
3

Test 28

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
3 2 1

correct output
3

user output
3

Test 29

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 1 2

correct output
2

user output
2