— Dark mode

Datatähti 2025 alku

Kortit I

  • Start: 2024-10-28 00:00:00
  • End: 2024-11-11 00:00:00
  • Contest has ended
CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit I
Sender:Kivvil
Submission time:2024-11-03 15:09:42 +0200
Language:Rust (2021)
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3details
#20.00 s2, 3details
#30.01 s3details
#40.01 s3details
#50.01 s3details
#60.01 s3details
#70.01 s3details
#80.01 s3details
#90.01 s3details
#100.01 s3details
#110.01 s3details
#120.01 s3details
#130.01 s3details
#140.01 s3details
#150.01 s3details
#160.03 s3details
#170.02 s3details
#180.02 s3details
#190.03 s3details
#200.03 s3details

Code

use std::{collections::HashSet, io::BufRead};
fn main() {
    let mut stdin_lines = std::io::stdin().lock().lines();
    let testien_maara: usize = stdin_lines
        .next()
        .unwrap()
        .unwrap()
        .parse()
        .expect("Invalidi testien lukumäärä");
 
    let testit: Vec<Testi> = stdin_lines
        .take(testien_maara)
        .map(|line| Testi::from_string(line.unwrap()))
        .collect();
 
    for testi in testit {
        match pelaa(testi) {
            Some((pelaaja_1_pelatut, pelaaja_2_pelatut)) => {
                println!("YES");
                let output1: String = pelaaja_1_pelatut
                    .into_iter()
                    .map(|kortti| format!("{} ", kortti.to_string()))
                    .collect();
                let output2: String = pelaaja_2_pelatut
                    .into_iter()
                    .map(|kortti| format!("{} ", kortti.to_string()))
                    .collect();
                let output2 = output2.trim_end();
                println!("{}", output1);
                println!("{}", output2);
            }
            None => println!("NO"),
        }
    }
}
 
fn pelaa(testi: Testi) -> Option<(Vec<u32>, Vec<u32>)> {
    let mut pelaaja_1_kortit: HashSet<u32> = (1..=testi.n).collect();
    let mut pelaaja_2_kortit: HashSet<u32> = (1..=testi.n).collect();
    let mut pelaaja_1_pelatut_kortit: Vec<u32> = vec![];
    let mut pelaaja_2_pelatut_kortit: Vec<u32> = vec![];
 
    // TODO: Spesiaalitapaus:
    // if testi.n == 4 && testi.pelaaja_1_pisteet == 2 && testi.pelaaja_2_pisteet == 2 {
    //     pelaaja_1_pelatut_kortit = vec![4, 2, 3, 1];
    //     pelaaja_2_pelatut_kortit = vec![3, 1, 4, 2];
    //     return Some((pelaaja_1_pelatut_kortit, pelaaja_2_pelatut_kortit));
    // } else if testi.n == 6 && testi.pelaaja_1_pisteet == 3 && testi.pelaaja_2_pisteet == 3 {
    //     pelaaja_1_pelatut_kortit = vec![2, 4, 6, 1, 3, 5];
    //     pelaaja_2_pelatut_kortit = vec![1, 3, 5, 2, 4, 6];
    //     return Some((pelaaja_1_pelatut_kortit, pelaaja_2_pelatut_kortit));
    // } else if testi.n == 8 && testi.pelaaja_1_pisteet == 4 && testi.pelaaja_2_pisteet == 4 {
    //     pelaaja_1_pelatut_kortit = vec![2, 4, 6, 8, 1, 3, 5, 7];
    //     pelaaja_2_pelatut_kortit = vec![1, 3, 5, 7, 2, 4, 6, 8];
    //     return Some((pelaaja_1_pelatut_kortit, pelaaja_2_pelatut_kortit));
    // }
 
    if testi.pelaaja_1_pisteet == testi.pelaaja_2_pisteet {
        for _i in 0..testi.pelaaja_1_pisteet {
            let pelaaja_1_max = *pelaaja_1_kortit.iter().max()?;
            let pelaaja_2_min = *pelaaja_2_kortit
                .iter()
                .filter(|k| **k < pelaaja_1_max)
                .max()?;
            if pelaaja_2_min == pelaaja_1_max {
                return None;
            }
            pelaaja_1_pelatut_kortit.push(pelaaja_1_max);
            pelaaja_2_pelatut_kortit.push(pelaaja_2_min);
            pelaaja_1_kortit.remove(&pelaaja_1_max);
            pelaaja_2_kortit.remove(&pelaaja_2_min);
 
            let pelaaja_2_max = *pelaaja_2_kortit.iter().max()?;
            let pelaaja_1_min = *pelaaja_1_kortit
                .iter()
                .filter(|k| **k < pelaaja_2_max)
                .max()?;
            if pelaaja_1_min == pelaaja_2_max {
                return None;
            }
            pelaaja_2_pelatut_kortit.push(pelaaja_2_max);
            pelaaja_1_pelatut_kortit.push(pelaaja_1_min);
            pelaaja_2_kortit.remove(&pelaaja_2_max);
            pelaaja_1_kortit.remove(&pelaaja_1_min);
        }
        let pelaaja_2_kortit_clone = pelaaja_2_kortit.clone();
        let pelaaja_1_kortit_clone = pelaaja_1_kortit.clone();
        let tasapelien_maara =
            testi.n as i32 - (testi.pelaaja_1_pisteet + testi.pelaaja_2_pisteet) as i32;
        let mut yhteiset_kortit: Vec<&u32> = pelaaja_1_kortit_clone
            .intersection(&pelaaja_2_kortit_clone)
            .collect::<Vec<&u32>>();
        yhteiset_kortit.sort();
        if tasapelien_maara == yhteiset_kortit.len() as i32 {
            for yhteinen_kortti in yhteiset_kortit {
                pelaaja_1_pelatut_kortit.push(*yhteinen_kortti);
                pelaaja_2_pelatut_kortit.push(*yhteinen_kortti);
                pelaaja_1_kortit.remove(yhteinen_kortti);
                pelaaja_2_kortit.remove(yhteinen_kortti);
            }
            return Some((pelaaja_1_pelatut_kortit, pelaaja_2_pelatut_kortit));
        } else {
            return None;
        }
    }
 
    // Etsitään molempien pakasta samanarvoiset kortit ja annetaan niitä niin pitkään, että
    // tasapelien määrä on saavutettu.
    let pelaaja_2_kortit_clone = pelaaja_2_kortit.clone();
    let pelaaja_1_kortit_clone = pelaaja_1_kortit.clone();
    let tasapelien_maara =
        testi.n as i32 - (testi.pelaaja_1_pisteet + testi.pelaaja_2_pisteet) as i32;
    let mut yhteiset_kortit = pelaaja_1_kortit_clone.intersection(&pelaaja_2_kortit_clone);
    if tasapelien_maara > 0 {
        for _ in 0..(testi.n - (testi.pelaaja_1_pisteet + testi.pelaaja_2_pisteet)) {
            let kortti = yhteiset_kortit.next()?;
            pelaaja_1_pelatut_kortit.push(*kortti);
            pelaaja_2_pelatut_kortit.push(*kortti);
            pelaaja_1_kortit.remove(&kortti);
            pelaaja_2_kortit.remove(&kortti);
        }
    }
 
    let pelaaja_1_aloittaa = testi.pelaaja_1_pisteet >= testi.pelaaja_2_pisteet;
    if pelaaja_1_aloittaa {
        for _ in 0..testi.pelaaja_1_pisteet {
            let pelaaja_1_max = *pelaaja_1_kortit.iter().max()?;
            let pelaaja_2_min = *pelaaja_2_kortit
                .iter()
                .filter(|k| **k < pelaaja_1_max)
                .max()?;
            if pelaaja_2_min == pelaaja_1_max {
                return None;
            }
            pelaaja_1_pelatut_kortit.push(pelaaja_1_max);
            pelaaja_2_pelatut_kortit.push(pelaaja_2_min);
            pelaaja_1_kortit.remove(&pelaaja_1_max);
            pelaaja_2_kortit.remove(&pelaaja_2_min);
        }
        for _ in 0..testi.pelaaja_2_pisteet {
            let pelaaja_2_max = *pelaaja_2_kortit.iter().max()?;
            let pelaaja_1_min = *pelaaja_1_kortit
                .iter()
                .filter(|k| **k < pelaaja_2_max)
                .max()?;
            if pelaaja_1_min == pelaaja_2_max {
                return None;
            }
            pelaaja_2_pelatut_kortit.push(pelaaja_2_max);
            pelaaja_1_pelatut_kortit.push(pelaaja_1_min);
            pelaaja_2_kortit.remove(&pelaaja_2_max);
            pelaaja_1_kortit.remove(&pelaaja_1_min);
        }
    } else {
        for _ in 0..testi.pelaaja_2_pisteet {
            let pelaaja_2_max = *pelaaja_2_kortit.iter().max()?;
            let pelaaja_1_min = *pelaaja_1_kortit
                .iter()
                .filter(|k| **k < pelaaja_2_max)
                .max()?;
            if pelaaja_1_min == pelaaja_2_max {
                return None;
            }
            pelaaja_2_pelatut_kortit.push(pelaaja_2_max);
            pelaaja_1_pelatut_kortit.push(pelaaja_1_min);
            pelaaja_2_kortit.remove(&pelaaja_2_max);
            pelaaja_1_kortit.remove(&pelaaja_1_min);
        }
        for _ in 0..testi.pelaaja_1_pisteet {
            let pelaaja_1_max = *pelaaja_1_kortit.iter().max()?;
            let pelaaja_2_min = *pelaaja_2_kortit
                .iter()
                .filter(|k| **k < pelaaja_1_max)
                .max()?;
            if pelaaja_2_min == pelaaja_1_max {
                return None;
            }
            pelaaja_1_pelatut_kortit.push(pelaaja_1_max);
            pelaaja_2_pelatut_kortit.push(pelaaja_2_min);
            pelaaja_1_kortit.remove(&pelaaja_1_max);
            pelaaja_2_kortit.remove(&pelaaja_2_min);
        }
    }
 
    if !pelaaja_1_kortit.is_empty() || !pelaaja_2_kortit.is_empty() {
        // Kaikkia kortteja ei pelattu loppuun.
        return None;
    }
 
    Some((pelaaja_1_pelatut_kortit, pelaaja_2_pelatut_kortit))
}
 
struct Testi {
    n: u32,
    pelaaja_1_pisteet: u32,
    pelaaja_2_pisteet: u32,
}
 
impl Testi {
    fn from_string(value: String) -> Self {
        let mut split = value.split(" ");
        Self {
            n: split
                .next()
                .unwrap()
                .parse()
                .expect("Invalidi korttien määrä"),
            pelaaja_1_pisteet: split
                .next()
                .unwrap()
                .parse()
                .expect("Invalidi pelaajan 1 pisteet"),
            pelaaja_2_pisteet: split
                .next()
                .unwrap()
                .parse()
                .expect("Invalidi pelaajan 2 pisteet"),
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
54
4 4 0
3 1 3
3 2 2
4 0 4
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 2

Group: 2, 3

Verdict:

input
284
6 1 0
5 0 2
7 1 5
7 7 5
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 
2 3 4 5 6 1 7 
...
view save

user output
NO
NO
YES
2 6 5 4 3 1 7 
2 7 6 5 4 3 1
...
view save

Test 3

Group: 3

Verdict:

input
955
14 2 10
12 2 5
10 4 9
14 1 13
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
YES
13 12 11 10 9 8 7 6 5 4 3 2 1 ...
view save

Test 4

Group: 3

Verdict:

input
869
17 12 9
16 8 4
15 9 9
17 11 15
...
view save

correct output
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 5

Group: 3

Verdict:

input
761
18 3 15
19 1 15
18 8 1
19 19 17
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
YES
9 11 5 18 17 16 15 14 13 12 10...
view save

Test 6

Group: 3

Verdict:

input
925
21 14 21
20 18 18
20 7 6
21 14 9
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 7

Group: 3

Verdict:

input
529
22 3 3
22 17 5
22 6 15
22 22 20
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
YES
22 21 20 19 18 17 1 2 3 4 5 6 ...
view save

Test 8

Group: 3

Verdict:

input
576
23 18 9
23 16 8
23 16 13
23 16 22
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 9

Group: 3

Verdict:

input
625
24 2 22
24 15 21
24 6 3
24 21 1
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
YES
14 17 24 23 22 21 20 19 18 16 ...
view save

Test 10

Group: 3

Verdict:

input
676
25 16 25
25 15 2
25 15 7
25 15 16
...
view save

correct output
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 11

Group: 3

Verdict:

input
729
26 2 18
26 14 18
26 5 18
26 19 13
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 12

Group: 3

Verdict:

input
784
27 26 7
27 14 0
27 14 5
27 14 14
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 13

Group: 3

Verdict:

input
841
28 26 16
28 13 19
28 5 8
28 26 4
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 14

Group: 3

Verdict:

input
900
29 24 15
29 13 2
29 13 7
29 13 16
...
view save

correct output
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 15

Group: 3

Verdict:

input
961
30 24 26
30 12 24
30 4 29
30 24 14
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 16

Group: 3

Verdict:

input
1000
15 12 6
33 18 30
44 4 26
6 6 5
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 17

Group: 3

Verdict:

input
1000
45 32 30
4 0 3
46 23 10
71 19 46
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 18

Group: 3

Verdict:

input
1000
51 29 37
75 11 72
5 2 4
31 8 26
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 19

Group: 3

Verdict:

input
1000
50 20 37
99 45 58
86 79 73
85 70 54
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 20

Group: 3

Verdict:

input
1000
26 23 5
73 53 59
64 47 41
80 75 55
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Tasks

A Pizzat-B Robotti-C Kortit I-D Kortit II-E Niitty-F Tikut-

Submissions (Kivvil)

2024-11-03 15:12:11 122024-11-03 15:09:42 122024-11-01 15:31:37 122024-11-01 15:29:04 122024-10-29 19:21:29 122024-10-29 19:05:17 122024-10-29 18:36:31 02024-10-29 16:56:01 0