CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:axka
Submission time:2023-11-07 17:29:00 +0200
Language:Rust
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#20.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#40.01 s1, 2details
#5ACCEPTED0.01 s1, 2details
#6ACCEPTED0.01 s1, 2details
#7ACCEPTED0.01 s1, 2details
#8ACCEPTED0.01 s1, 2details
#9ACCEPTED0.00 s1, 2details
#10ACCEPTED0.00 s1, 2details
#11ACCEPTED0.00 s1, 2details
#12ACCEPTED0.00 s1, 2details
#130.00 s1, 2details
#14ACCEPTED0.01 s1, 2details
#15ACCEPTED0.01 s1, 2details
#16--2details
#17--2details
#18--2details
#19--2details
#20--2details
#21--2details
#22--2details
#23--2details
#24--2details

Code

//! Input:
//! 5 6 13
//! 1 1 K
//! 5 1 K
//! 2 2 H
//! 4 2 H
//! 5 2 H
//! 2 6 K
//! 3 3 H
//! 3 4 K
//! 3 5 H
//! 3 6 K
//! 4 4 K
//! 2 5 H
//! 5 5 H
//! output:
//! -16
use std::io::stdin;
struct Saalis {
/// (a, b)
sijainti: (usize, usize),
/// c
kala: SaalisKala,
}
enum SaalisKala {
/// 'H', voitto/net: 1
Hauki,
/// 'K', sakko/fine: 10
Katkarapu,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Reikä {
/// 'T'
koko: usize,
kärki_ylös: bool,
sijainti: (usize, usize),
}
#[cfg(test)]
#[test]
fn test_mk_shape() {
// x
eprintln!("-=-=- 1: 1x1");
assert_eq!(
Reikä {
koko: 1,
kärki_ylös: true,
sijainti: (0, 0),
}
.mk_shape(),
vec![((0, 0), true)]
);
// x
eprintln!("-=-=- 1_offset: 1x1");
assert_eq!(
Reikä {
koko: 1,
kärki_ylös: true,
sijainti: (0, 1),
}
.mk_shape(),
vec![((0, 1), true)]
);
// x
// xx
eprintln!("-=-=- 2: 2x2");
assert_eq!(
Reikä {
koko: 2,
kärki_ylös: true,
sijainti: (0, 0),
}
.mk_shape(),
vec![
((0, 0), true),
((1, 0), false),
((0, 1), true),
((1, 1), true),
]
);
// x
// xx
eprintln!("-=-=- 2_offset: 2x2");
assert_eq!(
Reikä {
koko: 2,
kärki_ylös: true,
sijainti: (0, 1),
}
.mk_shape(),
vec![
((0, 1), false),
((1, 1), true),
((0, 2), true),
((1, 2), true),
]
);
// xx
// x
eprintln!("-=-=- 3: 2x2");
assert_eq!(
Reikä {
koko: 2,
kärki_ylös: false,
sijainti: (0, 0),
}
.mk_shape(),
vec![
((0, 0), true),
((1, 0), true),
((0, 1), true),
((1, 1), false),
]
);
// xxx
// xx
// x
eprintln!("-=-=- 4: 3x3");
assert_eq!(
Reikä {
koko: 3,
kärki_ylös: false,
sijainti: (3, 1),
}
.mk_shape(),
vec![
((3, 1), true),
((4, 1), true),
((5, 1), true),
((3, 2), false),
((4, 2), true),
((5, 2), true),
((3, 3), false),
((4, 3), true),
((5, 3), false),
]
);
}
#[cfg(test)]
#[test]
fn test_norm_x() {
{
// is_shifted_row = false
let dy = 0;
assert_eq!(Reikä::norm_x(dy, 0), 0); // x = 0.0
assert_eq!(Reikä::norm_x(dy, 1), 0); // x = 0.5
assert_eq!(Reikä::norm_x(dy, 2), 1); // x = 1.0
assert_eq!(Reikä::norm_x(dy, 3), 1); // x = 1.5
assert_eq!(Reikä::norm_x(dy, 4), 2); // x = 2.0
assert_eq!(Reikä::norm_x(dy, 5), 2); // x = 2.5
}
{
// is_shifted_row = true
let dy = 1;
assert_eq!(Reikä::norm_x(dy, 0), 0); // x = 0.5
assert_eq!(Reikä::norm_x(dy, 1), 1); // x = 1.0
assert_eq!(Reikä::norm_x(dy, 2), 1); // x = 1.5
assert_eq!(Reikä::norm_x(dy, 3), 2); // x = 2.0
assert_eq!(Reikä::norm_x(dy, 4), 2); // x = 2.5
assert_eq!(Reikä::norm_x(dy, 5), 3); // x = 3.0
}
}
/*fn terminal_interface() {
let size = 5;
let dy = 1;
let kärki_ylös = true;
let right_shift = if dy % 2 == 0 { dy + 1 } else { dy - 1 };
for n_row in 0..size {
let n_row = if kärki_ylös {
size - 1 - n_row
} else {
n_row
};
let mut line = String::new();
line.push('#');
let lpad = Reikä::norm_x(dy, n_row);
let rpad = Reikä::norm_x(right_shift, n_row);
for _ in 0..lpad {
line.push(' ');
}
for _ in 0..(size - n_row) {
line.push('x');
}
for _ in 0..rpad {
line.push(' ');
}
line.push('#');
println!("{line} - {n_row} -> {lpad}");
}
}*/
#[cfg(test)]
#[test]
fn test_leikkaa() {
let saaliit = vec![Saalis {
sijainti: (4, 4),
kala: SaalisKala::Katkarapu,
}];
let verkon_koko = (5, 5);
// |xxx |
// |xx |
// | x |
// | |
// | K|
eprintln!("-=-=- 1");
assert_eq!(
Reikä {
koko: 3,
kärki_ylös: false,
sijainti: (0, 0),
}
.leikkaa(&saaliit, verkon_koko),
Some(-10)
);
// |xxxxxx
// |xxxxx|
// | xxxx|
// | xxx |
// | xxK|
// x
eprintln!("-=-=- 2: out of bounds");
assert_eq!(
Reikä {
koko: verkon_koko.0.max(verkon_koko.1) + 1,
kärki_ylös: false,
sijainti: (0, 0),
}
.leikkaa(&saaliit, verkon_koko),
None
);
// | |
// | |
// | x |
// | xx|
// | xxxK|
eprintln!("-=-=- 3");
assert_eq!(
Reikä {
koko: 3,
kärki_ylös: true,
sijainti: (2, 2),
}
.leikkaa(&saaliit, verkon_koko),
Some(0)
);
// | x
// | |
// | |
// | |
// | K|
eprintln!("-=-=- 4: out of bounds");
assert_eq!(
Reikä {
koko: 1,
kärki_ylös: false,
sijainti: (verkon_koko.0, 0),
}
.leikkaa(&saaliit, verkon_koko),
None
);
// | |
// | |
// | |
// | |
// | K|
// x
eprintln!("-=-=- 5: out of bounds");
assert_eq!(
Reikä {
koko: 1,
kärki_ylös: false,
sijainti: (0, verkon_koko.1),
}
.leikkaa(&saaliit, verkon_koko),
None
);
}
impl Reikä {
fn norm_x(dy: usize, y: usize) -> usize {
(dy + y) / 2
}
fn mk_shape(&self) -> Vec<((usize, usize), bool)> {
let (dx, dy) = self.sijainti;
let mut v = vec![vec![((0, 0), false); self.koko]; self.koko];
for (y, row) in v.iter_mut().enumerate() {
// flip if kärki_ylös is true
let y_flipped = if self.kärki_ylös {
self.koko - 1 - y
} else {
y
};
let x_min = Reikä::norm_x(dy, y_flipped);
let x_max = x_min + self.koko - y_flipped - 1;
for (x, cell) in row.iter_mut().enumerate() {
*cell = ((dx + x, dy + y), x_min <= x && x <= x_max);
}
}
v.into_iter().flatten().collect()
}
/// Option::None: Mahdoton or error
/// Palauttaa saaliit muodon ulkopuolella
fn leikkaa(&self, saaliit: &[Saalis], (korkeus, leveys): (usize, usize)) -> Option<i32> {
{
// Out-of-bounds check
let p1 = self.sijainti;
let p2 = (p1.0 + self.koko - 1, p1.1 + self.koko - 1);
if p2.0 >= leveys || p2.1 >= korkeus {
return None;
}
}
let shape = self.mk_shape();
let mut pisteet = 0;
for x in 0..leveys {
for y in 0..korkeus {
if let Some((_, true)) = shape.iter().find(|(coord, _)| *coord == (x, y)) {
// on leikattu ulos
} else if let Some(saalis) = saaliit.iter().find(|saalis| saalis.sijainti == (x, y))
{
pisteet += match saalis.kala {
SaalisKala::Hauki => 1,
SaalisKala::Katkarapu => -10,
};
}
}
}
Some(pisteet)
}
}
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut lines = stdin().lines();
let ensimmäinen_rivi = lines
.next()
.unwrap()?
.split_ascii_whitespace()
.map(str::parse)
.collect::<Result<Vec<usize>, _>>()?;
// n, m, k
let (korkeus, leveys, n_saalis) = (
ensimmäinen_rivi[0],
ensimmäinen_rivi[1],
ensimmäinen_rivi[2],
);
let saaliit: Result<Vec<Saalis>, Box<dyn std::error::Error>> = lines
.by_ref()
.take(n_saalis)
.map(|rivi| {
let rivi = rivi?;
// Lue luvut rivistä
let mut sijainti = rivi.split_ascii_whitespace().take(2).map(str::parse);
let merkki = rivi.split_ascii_whitespace().skip(2).next().unwrap();
// IMPORTANT: x and y are flipped and start at one
let y: usize = sijainti.next().unwrap()?;
let x = sijainti.next().unwrap()?;
let (x, y) = (x - 1, y - 1);
Ok(Saalis {
sijainti: (x, y),
kala: match merkki {
"H" => SaalisKala::Hauki,
"K" => SaalisKala::Katkarapu,
_ => panic!("unexpected merkki {}", merkki),
},
})
})
.collect();
let saaliit = saaliit?;
let mut piste_lista = Vec::new();
for koko in 1..255 {
for kärki_ylös in [true, false] {
for x in 0..leveys {
for y in 0..korkeus {
let reikä = Reikä {
koko,
kärki_ylös,
sijainti: (x, y)
};
if let Some(pisteet) = reikä.leikkaa(&saaliit, (korkeus, leveys)) {
piste_lista.push(pisteet);
}
}
}
}
}
//println!("{:?}", piste_lista.iter().max_by_key(|x| x.0).unwrap());
println!("{}", piste_lista.iter().max().unwrap());
Ok(())
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
5 6 13
1 1 K
5 1 K
2 2 H
4 2 H
...

correct output
-16

user output
-16

Test 2

Group: 1, 2

Verdict:

input
5 6 7
1 5 K
4 6 K
2 4 H
2 5 H
...

correct output
0

user output
-5

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
5 6 7
5 5 K
2 6 K
2 4 H
2 5 H
...

correct output
0

user output
0

Test 4

Group: 1, 2

Verdict:

input
10 10 51
3 3 H
6 3 H
9 5 H
5 10 H
...

correct output
50

user output
49

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
10 10 52
3 5 H
3 1 H
9 6 H
2 8 H
...

correct output
40

user output
40

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
10 10 60
6 10 H
2 8 H
5 8 H
8 10 H
...

correct output
-15

user output
-15

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
10 10 60
4 7 H
7 4 H
4 10 H
3 6 H
...

correct output
60

user output
60

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
10 10 40
9 9 H
5 10 H
5 6 H
4 9 H
...

correct output
2

user output
2

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
1 1 0

correct output
0

user output
0

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 K

correct output
0

user output
0

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 H

correct output
0

user output
0

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
10 5 32
10 3 H
4 4 H
3 3 H
5 4 H
...

correct output
20

user output
20

Test 13

Group: 1, 2

Verdict:

input
5 10 32
5 9 H
2 4 H
2 9 H
2 5 H
...

correct output
28

user output
21

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
10 10 100
2 9 H
5 4 H
5 9 K
6 1 K
...

correct output
-439

user output
-439

Test 15

Group: 1, 2

Verdict: ACCEPTED

input
10 10 100
8 9 H
5 10 H
5 4 H
3 9 H
...

correct output
88

user output
88

Test 16

Group: 2

Verdict:

input
500 500 125000
125 261 K
84 78 K
11 200 K
481 246 K
...

correct output
-624270

user output
(empty)

Test 17

Group: 2

Verdict:

input
500 500 125100
16 61 H
37 62 H
459 125 H
318 476 H
...

correct output
124020

user output
(empty)

Test 18

Group: 2

Verdict:

input
500 500 249999
22 214 H
356 145 H
341 29 H
393 262 H
...

correct output
249999

user output
(empty)

Test 19

Group: 2

Verdict:

input
500 500 32000
30 81 H
315 34 H
78 112 H
367 166 H
...

correct output
10126

user output
(empty)

Test 20

Group: 2

Verdict:

input
500 500 126745
164 390 H
126 331 H
164 126 H
55 92 H
...

correct output
-104692

user output
(empty)

Test 21

Group: 2

Verdict:

input
500 500 71200
106 191 H
314 189 H
482 485 H
344 401 H
...

correct output
-335853

user output
(empty)

Test 22

Group: 2

Verdict:

input
500 500 67772
421 277 H
428 470 H
169 142 H
256 345 H
...

correct output
-208567

user output
(empty)

Test 23

Group: 2

Verdict:

input
500 500 27434
366 481 H
38 22 H
126 107 H
135 169 H
...

correct output
-57100

user output
(empty)

Test 24

Group: 2

Verdict:

input
500 500 93982
183 13 H
463 230 H
264 351 H
399 290 H
...

correct output
-52800

user output
(empty)