Submission #72330934

---

Source Code Expand

use std::io::{self, BufRead};
use std::time::Instant;

// Global constant N
const N: usize = 20;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Pos {
    r: usize,
    c: usize,
}

impl Pos {
    fn dist(&self, other: &Pos) -> i32 {
        (self.r as i32 - other.r as i32).abs() + (self.c as i32 - other.c as i32).abs()
    }
}

// Weights for board positions: Center -> Small, Edge -> Large
// Used in Phase 3
fn get_weight(p: Pos) -> i32 {
    let center = (N as f64 - 1.0) / 2.0;
    let dr = (p.r as f64 - center).abs();
    let dc = (p.c as f64 - center).abs();
    let max_dist = dr.max(dc);
    (max_dist * 100.0) as i32
}

struct Game {
    board: Vec<Vec<Option<usize>>>,
    stack: Vec<usize>,
    pos: Pos,
    moves: Vec<char>,
}

impl Game {
    fn new(board_input: Vec<Vec<usize>>) -> Self {
        let mut board = vec![vec![None; N]; N];
        for r in 0..N {
            for c in 0..N {
                board[r][c] = Some(board_input[r][c]);
            }
        }

        Game {
            board,
            stack: Vec::new(),
            pos: Pos { r: 0, c: 0 },
            moves: Vec::new(),
        }
    }

    // Operation 1: Move
    fn move_to_dir(&mut self, dir: char) {
        self.moves.push(dir);
        match dir {
            'U' => self.pos.r -= 1,
            'D' => self.pos.r += 1,
            'L' => self.pos.c -= 1,
            'R' => self.pos.c += 1,
            _ => panic!("Invalid move"),
        }
    }

    // Move to specific target coordinate (Basic Manhattan path)
    fn go_to(&mut self, target: Pos) {
        while self.pos != target {
            let dr = target.r as i32 - self.pos.r as i32;
            let dc = target.c as i32 - self.pos.c as i32;

            if dr < 0 { self.move_to_dir('U'); }
            else if dr > 0 { self.move_to_dir('D'); }
            else if dc < 0 { self.move_to_dir('L'); }
            else if dc > 0 { self.move_to_dir('R'); }
        }
    }

    // Operation 2: Pick (Z)
    fn pick(&mut self) {
        self.moves.push('Z');
        if let Some(val) = self.board[self.pos.r][self.pos.c] {
            self.board[self.pos.r][self.pos.c] = None;
            
            if let Some(&top) = self.stack.last() {
                if top == val {
                    self.stack.pop(); // Match!
                } else {
                    self.stack.push(val);
                }
            } else {
                self.stack.push(val);
            }
        }
    }

    // Operation 3: Place (X)
    fn place(&mut self) {
        // Can only place if stack is not empty and current pos is empty
        if self.stack.is_empty() { return; }
        if self.board[self.pos.r][self.pos.c].is_some() { return; }

        self.moves.push('X');
        let val = self.stack.pop().unwrap();
        self.board[self.pos.r][self.pos.c] = Some(val);
    }

    // Scan board for a specific value
    fn find_val_on_board(&self, val: usize) -> Option<Pos> {
        for r in 0..N {
            for c in 0..N {
                if self.board[r][c] == Some(val) {
                    return Some(Pos { r, c });
                }
            }
        }
        None
    }
    
    // Find pair logic for Greedy Phase (Phase 3)
    fn find_pair_on_board_exclude_current(&self, val: usize) -> Option<Pos> {
        for r in 0..N {
            for c in 0..N {
                if self.board[r][c] == Some(val) {
                     if r != self.pos.r || c != self.pos.c {
                        return Some(Pos { r, c });
                     }
                }
            }
        }
        None
    }

    // Phase 3 Helper: Max cards on path
    fn max_cards_on_path(&self, start: Pos, end: Pos) -> i32 {
        let dr = (end.r as i32 - start.r as i32).signum();
        let dc = (end.c as i32 - start.c as i32).signum();
        
        let rows = (start.r as i32 - end.r as i32).abs() as usize + 1;
        let cols = (start.c as i32 - end.c as i32).abs() as usize + 1;
        
        let mut dp = vec![vec![-1; cols]; rows];
        
        for i in 0..rows {
            for j in 0..cols {
                let r = (start.r as i32 + i as i32 * dr) as usize;
                let c = (start.c as i32 + j as i32 * dc) as usize;
                
                let has_card = if (r == start.r && c == start.c) { 0 } 
                               else if self.board[r][c].is_some() { 1 } 
                               else { 0 };
                
                let from_top = if i > 0 { dp[i-1][j] } else { -1 };
                let from_left = if j > 0 { dp[i][j-1] } else { -1 };
                
                if i == 0 && j == 0 {
                    dp[i][j] = 0;
                } else {
                    let prev = from_top.max(from_left);
                    if prev != -1 {
                        dp[i][j] = prev + has_card;
                    }
                }
            }
        }
        dp[rows-1][cols-1]
    }
}

// Xorshift random number generator
struct Xorshift {
    seed: u64,
}

impl Xorshift {
    fn new(seed: u64) -> Self {
        Self { seed }
    }
    
    fn next(&mut self) -> u64 {
        let mut x = self.seed;
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        self.seed = x;
        x
    }
    
    // Generate random number in [start, end)
    fn gen_range(&mut self, start: usize, end: usize) -> usize {
        if start >= end { return start; }
        (self.next() as usize % (end - start)) + start
    }
}

// Run full simulation with given pick flags for the spiral phase
// Returns (move_count, output_string_moves)
fn run_simulation(input_grid: &Vec<Vec<usize>>, spiral_targets: &Vec<Pos>, pick_flags: &Vec<bool>) -> (usize, Vec<char>) {
    let mut game = Game::new(input_grid.clone());

    // ==========================================
    // Phase 1: Spiral Collection
    // Use flags to determine whether to pick or skip
    // ==========================================
    for (i, target) in spiral_targets.iter().enumerate() {
        game.go_to(*target);
        if game.board[game.pos.r][game.pos.c].is_some() {
            if pick_flags[i] {
                game.pick();
            }
        }
    }

    // ==========================================
    // Phase 2: Stack Unloading
    // Match if possible, otherwise place at optimal empty spot
    // ==========================================
    let center_r = (N as f64 - 1.0) / 2.0;
    let center_c = (N as f64 - 1.0) / 2.0;

    while !game.stack.is_empty() {
        let top_val = *game.stack.last().unwrap();
        
        if let Some(target) = game.find_val_on_board(top_val) {
            game.go_to(target);
            game.pick();
        } else {
            let mut best_spot: Option<Pos> = None;
            let mut min_travel_dist = i32::MAX;
            let mut min_center_dist = f64::MAX;

            for r in 0..N {
                for c in 0..N {
                    if game.board[r][c].is_none() {
                        let p = Pos { r, c };
                        let travel = game.pos.dist(&p);
                        let d_center = ((r as f64 - center_r).powi(2) + (c as f64 - center_c).powi(2)).sqrt();

                        if travel < min_travel_dist {
                            min_travel_dist = travel;
                            min_center_dist = d_center;
                            best_spot = Some(p);
                        } else if travel == min_travel_dist {
                            if d_center < min_center_dist {
                                min_center_dist = d_center;
                                best_spot = Some(p);
                            }
                        }
                    }
                }
            }

            if let Some(target) = best_spot {
                game.go_to(target);
                game.place();
            } else {
                break;
            }
        }
    }

    // ==========================================
    // Phase 3: Greedy Cleanup
    // ==========================================
    loop {
        let mut remaining = 0;
        for r in 0..N {
            for c in 0..N {
                if game.board[r][c].is_some() { remaining += 1; }
            }
        }
        if remaining == 0 && game.stack.is_empty() {
            break;
        }

        if game.stack.is_empty() {
            let mut best_target: Option<Pos> = None;
            let mut best_dist = i32::MAX;
            let mut best_weight = -1;

            for r in 0..N {
                for c in 0..N {
                    if game.board[r][c].is_some() {
                        let p = Pos { r, c };
                        let d = game.pos.dist(&p);
                        let w = get_weight(p);
                        
                        if d < best_dist {
                            best_dist = d;
                            best_weight = w;
                            best_target = Some(p);
                        } else if d == best_dist {
                            if w > best_weight {
                                best_weight = w;
                                best_target = Some(p);
                            }
                        }
                    }
                }
            }
            
            if let Some(target) = best_target {
                while game.pos != target {
                    let curr = game.pos;
                    let dr = target.r as i32 - curr.r as i32;
                    let dc = target.c as i32 - curr.c as i32;
                    
                    let mut moves = Vec::new();
                    if dr < 0 { moves.push(('U', Pos{r: curr.r-1, c: curr.c})); }
                    if dr > 0 { moves.push(('D', Pos{r: curr.r+1, c: curr.c})); }
                    if dc < 0 { moves.push(('L', Pos{r: curr.r, c: curr.c-1})); }
                    if dc > 0 { moves.push(('R', Pos{r: curr.r, c: curr.c+1})); }
                    
                    let mut best_move = moves[0];
                    let mut max_cards = -1;
                    
                    for m in moves {
                        let count = game.max_cards_on_path(m.1, target);
                        if count > max_cards {
                            max_cards = count;
                            best_move = m;
                        }
                    }
                    game.move_to_dir(best_move.0);
                }
                game.pick();
            }

        } else {
            let top_val = *game.stack.last().unwrap();
            
            loop {
                if game.stack.is_empty() || *game.stack.last().unwrap() != top_val {
                    break;
                }
                
                let target_opt = game.find_pair_on_board_exclude_current(top_val);
                
                if target_opt.is_none() { break; }
                let target = target_opt.unwrap();
                
                if game.pos == target {
                    game.pick();
                    break;
                }
                
                let curr = game.pos;
                let dr = target.r as i32 - curr.r as i32;
                let dc = target.c as i32 - curr.c as i32;
                
                let mut moves = Vec::new();
                if dr < 0 { moves.push(('U', Pos{r: curr.r-1, c: curr.c})); }
                if dr > 0 { moves.push(('D', Pos{r: curr.r+1, c: curr.c})); }
                if dc < 0 { moves.push(('L', Pos{r: curr.r, c: curr.c-1})); }
                if dc > 0 { moves.push(('R', Pos{r: curr.r, c: curr.c+1})); }
                
                let mut best_move = moves[0];
                let mut max_cards = -1;
                
                for m in moves {
                    let count = game.max_cards_on_path(m.1, target);
                    if count > max_cards {
                        max_cards = count;
                        best_move = m;
                    }
                }
                
                game.move_to_dir(best_move.0);
                
                if let Some(card_here) = game.board[game.pos.r][game.pos.c] {
                    if card_here != top_val {
                        let dist_to_current_target = game.pos.dist(&target);
                        if let Some(pair_pos) = game.find_pair_on_board_exclude_current(card_here) {
                            let dist_to_new_target = game.pos.dist(&pair_pos);
                            if dist_to_new_target < dist_to_current_target {
                                game.pick(); 
                                break; 
                            }
                        }
                    } else {
                        game.pick();
                        break;
                    }
                }
            }
        }
    }

    let move_count = game.moves.iter().filter(|&&c| c == 'U' || c == 'D' || c == 'L' || c == 'R').count();
    (move_count, game.moves)
}

fn solve() {
    let start_time = Instant::now();
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    
    // Read N (20)
    let _n_str = lines.next().unwrap().unwrap();
    
    // Read Grid
    let mut input_grid = vec![vec![0; N]; N];
    for r in 0..N {
        let line = lines.next().unwrap().unwrap();
        let nums: Vec<usize> = line.split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect();
        for c in 0..N {
            input_grid[r][c] = nums[c];
        }
    }

    // Generate spiral coordinates for outer rings
    let mut spiral_targets = Vec::new();
    for layer in 0..7 {
        // Top edge (Left to Right)
        for c in layer..(N - layer - 1) { spiral_targets.push(Pos{r: layer, c}); }
        // Right edge (Top to Bottom)
        for r in layer..(N - layer - 1) { spiral_targets.push(Pos{r, c: N - 1 - layer}); }
        // Bottom edge (Right to Left)
        for c in (layer + 1..=(N - 1 - layer)).rev() { spiral_targets.push(Pos{r: N - 1 - layer, c}); }
        // Left edge (Bottom to Top)
        for r in (layer + 1..=(N - 1 - layer)).rev() { spiral_targets.push(Pos{r, c: layer}); }
    }

    // Hill Climbing Initialization
    let mut rng = Xorshift::new(123456789);
    let mut current_flags = vec![true; spiral_targets.len()];
    
    // Initial solution
    let (mut best_score, mut best_moves) = run_simulation(&input_grid, &spiral_targets, &current_flags);

    // Hill Climbing Loop (1.95s limit)
    while start_time.elapsed().as_secs_f64() < 1.95 {
        // Pick 1 to 3 indices to flip
        let num_changes = rng.gen_range(1, 4);
        let mut changed_indices = Vec::with_capacity(num_changes);
        
        // Apply changes
        for _ in 0..num_changes {
            let idx = rng.gen_range(0, spiral_targets.len());
            current_flags[idx] = !current_flags[idx];
            changed_indices.push(idx);
        }
        
        // Evaluate
        let (score, moves) = run_simulation(&input_grid, &spiral_targets, &current_flags);
        
        if score < best_score {
            // Adopt new state
            best_score = score;
            best_moves = moves;
        } else {
            // Revert changes
            for idx in changed_indices {
                current_flags[idx] = !current_flags[idx];
            }
        }
    }

    // Output best moves found
    for c in best_moves {
        println!("{}", c);
    }
}

fn main() {
    solve();
}

Submission Info

Compile Error

warning: unnecessary parentheses around `if` condition
   --> src/main.rs:148:35
    |
148 |                 let has_card = if (r == start.r && c == start.c) { 0 } 
    |                                   ^                            ^
    |
    = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
    |
148 -                 let has_card = if (r == start.r && c == start.c) { 0 } 
148 +                 let has_card = if r == start.r && c == start.c { 0 } 
    |

Judge Result