Robotti

use core::panic;
use std::alloc::{alloc, dealloc, handle_alloc_error, Layout};
use std::io::stdin;
use std::ptr::null_mut;

#[derive(PartialEq, Eq)]
pub enum Room {
    Empty,
    HasCoin,
}

pub struct LinkedListNode<T> {
    pub next: *mut LinkedListNode<T>,
    pub prev: *mut LinkedListNode<T>,
    pub data: T,
}

impl<T> LinkedListNode<T> {
    /// Removes this linked list node
    pub fn remove_this_element(&mut self) {
        unsafe {
            if !self.prev.is_null() {
                (*self.prev).next = self.next;
            }
            if !self.next.is_null() {
                (*self.next).prev = self.prev;
            }
            dealloc(
                self as *mut LinkedListNode<T> as *mut u8,
                Layout::new::<*mut LinkedListNode<T>>(),
            );
        }
    }
}

pub struct LinkedListIter<T> {
    address: *mut LinkedListNode<T>,
    first_node: *mut LinkedListNode<T>,
}

impl<T> Iterator for LinkedListIter<T> {
    type Item = *mut LinkedListNode<T>;
    fn next(&mut self) -> Option<Self::Item> {
        if self.address.is_null() {
            self.address = self.first_node;
            None
        } else {
            let v = Some(self.address);
            self.address = unsafe { (*self.address).next };
            v
        }
    }
}

impl<T> LinkedListIter<T> {
    #[inline]
    pub fn new(first_node: *mut LinkedListNode<T>) -> LinkedListIter<T> {
        LinkedListIter {
            address: first_node,
            first_node,
        }
    }
    #[inline]
    pub fn go_to_address(&mut self, address: *mut LinkedListNode<T>) {
        self.address = address;
    }
}

pub fn fast_method(mut coins: Vec<isize>, mut robot_position: isize) -> (isize, usize) {
    coins.sort_unstable();

    let mut first_coin: *mut LinkedListNode<isize> = null_mut();
    let mut current_coin: *mut LinkedListNode<isize> = null_mut();
    let mut prev_coin: *mut LinkedListNode<isize> = null_mut();
    let mut is_first_coin = true;
    for coin in coins {
        current_coin =
            unsafe { alloc(Layout::new::<LinkedListNode<isize>>()) } as *mut LinkedListNode<isize>;
        if current_coin.is_null() {
            handle_alloc_error(Layout::new::<LinkedListNode<isize>>());
        }
        if is_first_coin {
            first_coin = current_coin;
            unsafe {
                (*first_coin).prev = null_mut() as *mut LinkedListNode<isize>;
            }
            is_first_coin = false;
        } else {
            unsafe {
                (*prev_coin).next = current_coin;
                (*current_coin).prev = prev_coin;
            }
        }
        unsafe {
            (*current_coin).data = coin;
            (*current_coin).next = null_mut();
        }
        prev_coin = current_coin;
    }

    if robot_position == -1 {
        panic!()
    }
    let mut num_coins_collected = 0;
    let mut num_steps_taken = 0;
    let mut coin_iter = LinkedListIter::new(first_coin);
    let mut coin_found = false;
    for coin in &mut coin_iter {
        if unsafe { (*coin).data } > robot_position {
            if unsafe { (*coin).prev }.is_null() {
                coin_iter.go_to_address(coin);
            } else {
                coin_iter.go_to_address(unsafe { (*coin).prev });
            }
            coin_found = true;
            break;
        }
    }
    // There is no coin at a position to the right of the robot
    if !coin_found {
        coin_iter.go_to_address(current_coin);
    }
    loop {
        let (closest_coin, closest_coin_dis);

        let prev_coin = match coin_iter.next() {
            None => break,
            Some(c) => unsafe { &mut *c },
        };
        let disp = robot_position.abs_diff(prev_coin.data);
        match coin_iter.next() {
            None => {
                closest_coin = prev_coin;
                closest_coin_dis = disp;
            }
            Some(c) => {
                let c = unsafe { &mut *c };
                let disc = robot_position.abs_diff(c.data);
                if disc < disp {
                    closest_coin = c;
                    closest_coin_dis = disc;
                } else if disc > disp {
                    closest_coin = prev_coin;
                    closest_coin_dis = disp;
                } else {
                    break;
                }
            }
        }

        robot_position = closest_coin.data;
        if closest_coin.prev.is_null() {
            coin_iter.go_to_address(closest_coin.next);
        } else {
            coin_iter.go_to_address(closest_coin.prev);
        }
        closest_coin.remove_this_element();

        num_coins_collected += 1;
        num_steps_taken += closest_coin_dis;
    }
    (num_steps_taken as isize, num_coins_collected)
}

fn main() {
    let mut n = String::new();
    stdin().read_line(&mut n).unwrap();
    let room_count = n.trim().parse::<usize>().unwrap();
    let mut room_map = String::new();
    stdin().read_line(&mut room_map).unwrap();
    let mut robot_position: isize = -1;
    let rooms =
        room_map[0..room_count]
            .chars()
            .enumerate()
            .map(|(index, room_desc)| match room_desc {
                '*' => Room::HasCoin,
                '.' => Room::Empty,
                'R' => {
                    robot_position = index as isize;
                    Room::Empty
                }
                _ => panic!(),
            });

    let mut coins = Vec::new();
    for (index, room) in rooms.enumerate() {
        if room == Room::HasCoin {
            coins.push(index as isize);
        }
    }

    let answer = fast_method(coins, robot_position);
    println!("{} {}", answer.0, answer.1);
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 1, 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 1, 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED