Task: | Uolevin kalansaalis |
Sender: | Roopekt |
Submission time: | 2023-11-12 13:04:58 +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 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.00 s | 1, 2 | details |
#7 | ACCEPTED | 0.00 s | 1, 2 | details |
#8 | WRONG ANSWER | 0.00 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 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#15 | WRONG ANSWER | 0.00 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 |
Compiler report
warning: function `get_price_of_optimal_downwards_cut` is never used --> input/code.rs:64:4 | 64 | fn get_price_of_optimal_downwards_cut(price_map: &PriceMap, top_left_sticking_out: bool) -> i32 { | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: associated function `min_point_price` is never used --> input/code.rs:41:12 | 41 | pub fn min_point_price(&self) -> i32 { | ^^^^^^^^^^^^^^^ warning: 2 warnings emitted
Code
use std::io::stdin;use std::cmp::min;#[derive(Debug, Clone)]struct PriceMap {width: usize,height: usize,map: Vec<Vec<i32>>,}impl PriceMap {pub fn new(width: usize, height: usize) -> Self {Self {width,height,map: vec![vec![0; width]; height]//array of rows to increase cache hit rate}}#[inline(always)]pub fn get(&self, x: usize, y: usize) -> i32 {self.map[y][x]}#[inline(always)]pub fn set(&mut self, x: usize, y: usize, price: i32) {self.map[y][x] = price;}pub fn get_safe(&self, x: usize, y: usize) -> Option<i32> {if x >= self.width || y >= self.height {return None;}Some(self.map[y][x])}// pub fn empty_map_with_same_size(&self) -> Self {// Self::new(self.width, self.height)// }pub fn min_point_price(&self) -> i32 {*self.map.iter().map(|row| row.iter()).flatten().min().unwrap()}pub fn flip(&mut self) {let max_y = self.height - 1;for y in 0..self.height {for x in 0..self.width {let a = self.get(x, y);let b = self.get(x, max_y - y);self.set(x, y, b);self.set(x, max_y - y, a);}}}}//only checks downwards pointing trianglesfn get_price_of_optimal_downwards_cut(price_map: &PriceMap, top_left_sticking_out: bool) -> i32 {let mut triangle_price_map = price_map.clone();let mut line_price_map = price_map.clone();let mut best_price = price_map.min_point_price();let max_triangle_size = min(price_map.width, price_map.height);let parity_term = if top_left_sticking_out { 0 } else { 1 };for triangle_size in 2..=max_triangle_size {let max_x = price_map.width - triangle_size;let max_y = price_map.height - triangle_size;for y in 0..=max_y {let triangle_x_offset = (y + parity_term) % 2;for x in 0..=max_x {let point_price = price_map.get(x, y);let line_price = line_price_map.get(x + 1, y);let triangle_price = triangle_price_map.get(x + triangle_x_offset, y + 1);let new_line_price = line_price + point_price;let new_triangle_price = triangle_price + new_line_price;line_price_map.set(x, y, new_line_price);triangle_price_map.set(x, y, new_triangle_price);best_price = min(best_price, new_triangle_price);}}}best_price}fn get_price_of_optimal_cut(mut price_map: PriceMap) -> i32 {let mut optimal_cut_price = get_price_of_optimal_downwards_cut_naive(&price_map, true);price_map.flip();optimal_cut_price = min(optimal_cut_price, get_price_of_optimal_downwards_cut_naive(&price_map, price_map.height % 2 == 1));optimal_cut_price}fn main() {let mut input = stdin().lines();let line = input.next().unwrap().unwrap();let mut split = line.split_whitespace();let height: usize = split.next().unwrap().parse().unwrap();let width: usize = split.next().unwrap().parse().unwrap();let amount_of_fish: usize = split.next().unwrap().parse().unwrap();let mut price_map = PriceMap::new(width, height);let mut total_price: i32 = 0;for line_result in input.take(amount_of_fish) {let line = line_result.unwrap();let mut split = line.split_whitespace();let y: usize = split.next().unwrap().parse::<usize>().unwrap() - 1;let x: usize = split.next().unwrap().parse::<usize>().unwrap() - 1;let fish_type = split.next().unwrap();let price: i32 = match fish_type {"H" => 1,"K" => -10,_ => panic!("unknown fish type")};price_map.set(x, y, price);total_price += price;}let best_price = total_price - get_price_of_optimal_cut(price_map);println!("{best_price}");}fn get_price_of_optimal_downwards_cut_naive(price_map: &PriceMap, top_left_sticking_out: bool) -> i32 {let parity_term = if top_left_sticking_out { 0 } else { 1 };let mut best_price = i32::MAX;for triangle_size in 1..=min(price_map.width, price_map.height) {for corner_x in 0..price_map.width {for corner_y in 0..price_map.height {match get_triangle_price_naive(&price_map, corner_x, corner_y, triangle_size, parity_term) {Some(price) => best_price = min(best_price, price),None => {}}}}}best_price}fn get_triangle_price_naive(price_map: &PriceMap, corner_x: usize, corner_y: usize, triangle_size: usize, parity_term: usize) -> Option<i32> {let mut total_price = 0;for internal_y in 0..triangle_size {for internal_x in 0..=(triangle_size-1 - internal_y) {let y = corner_y + internal_y;let x_offset = ((y + parity_term) / 2) - ((corner_y + parity_term) / 2);let x = corner_x + x_offset + internal_x;match price_map.get_safe(x, y) {Some(price) => total_price += price,None => return None};}}Some(total_price)}
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: ACCEPTED
input |
---|
10 10 51 3 3 H 6 3 H 9 5 H 5 10 H ... |
correct output |
---|
50 |
user output |
---|
50 |
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: WRONG ANSWER
input |
---|
10 10 40 9 9 H 5 10 H 5 6 H 4 9 H ... |
correct output |
---|
2 |
user output |
---|
12 |
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 |
---|
20 |
Test 14
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
10 10 100 2 9 H 5 4 H 5 9 K 6 1 K ... |
correct output |
---|
-439 |
user output |
---|
-450 |
Test 15
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
10 10 100 8 9 H 5 10 H 5 4 H 3 9 H ... |
correct output |
---|
88 |
user output |
---|
90 |
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) |