Task: | Uolevin kalansaalis |
Sender: | axka |
Submission time: | 2023-11-07 17:29:00 +0200 |
Language: | Rust |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | WRONG ANSWER | 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.00 s | 1, 2 | details |
#10 | ACCEPTED | 0.00 s | 1, 2 | details |
#11 | ACCEPTED | 0.00 s | 1, 2 | details |
#12 | ACCEPTED | 0.00 s | 1, 2 | details |
#13 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#14 | ACCEPTED | 0.01 s | 1, 2 | details |
#15 | ACCEPTED | 0.01 s | 1, 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 2 | details |
#18 | TIME LIMIT EXCEEDED | -- | 2 | details |
#19 | TIME LIMIT EXCEEDED | -- | 2 | details |
#20 | TIME LIMIT EXCEEDED | -- | 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | TIME LIMIT EXCEEDED | -- | 2 | details |
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://! -16use std::io::stdin;struct Saalis {/// (a, b)sijainti: (usize, usize),/// ckala: SaalisKala,}enum SaalisKala {/// 'H', voitto/net: 1Hauki,/// 'K', sakko/fine: 10Katkarapu,}#[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() {// xeprintln!("-=-=- 1: 1x1");assert_eq!(Reikä {koko: 1,kärki_ylös: true,sijainti: (0, 0),}.mk_shape(),vec![((0, 0), true)]);// xeprintln!("-=-=- 1_offset: 1x1");assert_eq!(Reikä {koko: 1,kärki_ylös: true,sijainti: (0, 1),}.mk_shape(),vec![((0, 1), true)]);// x// xxeprintln!("-=-=- 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// xxeprintln!("-=-=- 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// xeprintln!("-=-=- 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// xeprintln!("-=-=- 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 = falselet dy = 0;assert_eq!(Reikä::norm_x(dy, 0), 0); // x = 0.0assert_eq!(Reikä::norm_x(dy, 1), 0); // x = 0.5assert_eq!(Reikä::norm_x(dy, 2), 1); // x = 1.0assert_eq!(Reikä::norm_x(dy, 3), 1); // x = 1.5assert_eq!(Reikä::norm_x(dy, 4), 2); // x = 2.0assert_eq!(Reikä::norm_x(dy, 5), 2); // x = 2.5}{// is_shifted_row = truelet dy = 1;assert_eq!(Reikä::norm_x(dy, 0), 0); // x = 0.5assert_eq!(Reikä::norm_x(dy, 1), 1); // x = 1.0assert_eq!(Reikä::norm_x(dy, 2), 1); // x = 1.5assert_eq!(Reikä::norm_x(dy, 3), 2); // x = 2.0assert_eq!(Reikä::norm_x(dy, 4), 2); // x = 2.5assert_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|// xeprintln!("-=-=- 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|// xeprintln!("-=-=- 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 truelet 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 ulkopuolellafn leikkaa(&self, saaliit: &[Saalis], (korkeus, leveys): (usize, usize)) -> Option<i32> {{// Out-of-bounds checklet 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, klet (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 onelet 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: WRONG ANSWER
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: WRONG ANSWER
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: WRONG ANSWER
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
500 500 93982 183 13 H 463 230 H 264 351 H 399 290 H ... |
correct output |
---|
-52800 |
user output |
---|
(empty) |