Task: | Uolevin kalansaalis |
Sender: | Roopekt |
Submission time: | 2023-11-12 14:07:24 +0200 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 37 |
#2 | ACCEPTED | 63 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 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 | ACCEPTED | 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 | ACCEPTED | 0.00 s | 1, 2 | details |
#14 | ACCEPTED | 0.00 s | 1, 2 | details |
#15 | ACCEPTED | 0.00 s | 1, 2 | details |
#16 | ACCEPTED | 0.45 s | 2 | details |
#17 | ACCEPTED | 0.45 s | 2 | details |
#18 | ACCEPTED | 0.47 s | 2 | details |
#19 | ACCEPTED | 0.44 s | 2 | details |
#20 | ACCEPTED | 0.45 s | 2 | details |
#21 | ACCEPTED | 0.44 s | 2 | details |
#22 | ACCEPTED | 0.44 s | 2 | details |
#23 | ACCEPTED | 0.44 s | 2 | details |
#24 | ACCEPTED | 0.45 s | 2 | details |
Compiler report
warning: function `get_price_of_optimal_cut_naive` is never used --> input/code.rs:136:4 | 136 | fn get_price_of_optimal_cut_naive(price_map: PriceMap) -> i32 { | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: function `get_triangle_price_naive` is never used --> input/code.rs:155:4 | 155 | fn get_triangle_price_naive(price_map: &PriceMap, corner_x: usize, corner_y: usize, triangle_size: usize, flipped: bool) -> Option<i32> { | ^^^^^^^^^^^^^^^^^^^^^^^^ warning: associated function `get_safe` is never used --> input/code.rs:29:12 | 29 | pub fn get_safe(&self, x: usize, y: usize) -> Option<i32> { | ^^^^^^^^ warning: 3 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 / 2) {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(&price_map, true);price_map.flip();optimal_cut_price = min(optimal_cut_price, get_price_of_optimal_downwards_cut(&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_cut_naive(price_map: PriceMap) -> i32 {let mut best_price = i32::MAX;for flipped in [false, true] {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, flipped) {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, flipped: bool) -> 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 = if flipped { corner_y.wrapping_sub(internal_y) } else { corner_y + internal_y };let x_offset = ((corner_y + internal_y) / 2) - (corner_y / 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)}#[cfg(test)]mod tests {use super::*;use rand::prelude::*;use rand::seq::SliceRandom;#[test]fn naive_and_efficient_agree() {const SEED: u64 = 13258927485903104053;let mut rng = StdRng::seed_from_u64(SEED);for i in 0..1000 {let price_map = get_random_price_map(&mut rng);let expected = get_price_of_optimal_cut_naive(price_map.clone());let actual = get_price_of_optimal_cut(price_map.clone());assert_eq!(expected, actual, "Subtest {i} failed.");}}fn get_random_price_map(rng: &mut StdRng) -> PriceMap {let width = rng.gen_range(1..=10);let height = rng.gen_range(1..=10);let mut price_map = PriceMap::new(width, height);for x in 0..width {for y in 0..height {let price: i32 = *[-10, 0, 1].choose(rng).unwrap();price_map.set(x, y, price);}}price_map}}
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: ACCEPTED
input |
---|
5 6 7 1 5 K 4 6 K 2 4 H 2 5 H ... |
correct output |
---|
0 |
user output |
---|
0 |
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: 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: ACCEPTED
input |
---|
5 10 32 5 9 H 2 4 H 2 9 H 2 5 H ... |
correct output |
---|
28 |
user output |
---|
28 |
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: ACCEPTED
input |
---|
500 500 125000 125 261 K 84 78 K 11 200 K 481 246 K ... |
correct output |
---|
-624270 |
user output |
---|
-624270 |
Test 17
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 125100 16 61 H 37 62 H 459 125 H 318 476 H ... |
correct output |
---|
124020 |
user output |
---|
124020 |
Test 18
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 249999 22 214 H 356 145 H 341 29 H 393 262 H ... |
correct output |
---|
249999 |
user output |
---|
249999 |
Test 19
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 32000 30 81 H 315 34 H 78 112 H 367 166 H ... |
correct output |
---|
10126 |
user output |
---|
10126 |
Test 20
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 126745 164 390 H 126 331 H 164 126 H 55 92 H ... |
correct output |
---|
-104692 |
user output |
---|
-104692 |
Test 21
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 71200 106 191 H 314 189 H 482 485 H 344 401 H ... |
correct output |
---|
-335853 |
user output |
---|
-335853 |
Test 22
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 67772 421 277 H 428 470 H 169 142 H 256 345 H ... |
correct output |
---|
-208567 |
user output |
---|
-208567 |
Test 23
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 27434 366 481 H 38 22 H 126 107 H 135 169 H ... |
correct output |
---|
-57100 |
user output |
---|
-57100 |
Test 24
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 93982 183 13 H 463 230 H 264 351 H 399 290 H ... |
correct output |
---|
-52800 |
user output |
---|
-52800 |