Submission #75295136

---

Source Code Expand

use proconio::{fastout, input};
use rand::seq::SliceRandom;
use rand::Rng;
use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;
use std::collections::HashMap;
use std::time::Instant;

const R: usize = 10;
const DEP_CAPACITY: usize = 15;
const SID_CAPACITY: usize = 20;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct FixedLine {
    data: [u8; 20],
    len: usize,
}

impl FixedLine {
    fn new() -> Self {
        Self {
            data: [0; 20],
            len: 0,
        }
    }
    fn push(&mut self, val: u8) {
        self.data[self.len] = val;
        self.len += 1;
    }
    fn pop(&mut self) -> Option<u8> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            Some(self.data[self.len])
        }
    }
    fn is_empty(&self) -> bool {
        self.len == 0
    }
    fn len(&self) -> usize {
        self.len
    }
}

impl std::ops::Index<usize> for FixedLine {
    type Output = u8;
    fn index(&self, index: usize) -> &Self::Output {
        &self.data[index]
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct State {
    d: [FixedLine; R],
    s: [FixedLine; R],
    hash: u64,
}

struct ZobristHasher {
    table: [[[[u64; 100]; 20]; 10]; 2],
}

impl ZobristHasher {
    fn new(rng: &mut ChaCha8Rng) -> Self {
        let mut table = [[[[0; 100]; 20]; 10]; 2];
        for t in 0..2 {
            for i in 0..10 {
                for p in 0..20 {
                    for v in 0..100 {
                        table[t][i][p][v] = rng.r#gen();
                    }
                }
            }
        }
        Self { table }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Move {
    type_: u8,
    i: u8,
    j: u8,
    k: u8,
}

impl Move {
    fn new(type_: usize, i: usize, j: usize, k: usize) -> Self {
        Self {
            type_: type_ as u8,
            i: i as u8,
            j: j as u8,
            k: k as u8,
        }
    }
}

#[derive(Clone, Debug)]
struct Input {
    y: [[usize; 10]; R],
}

struct Output {
    turns: Vec<Vec<Move>>,
}

impl Output {
    fn print(&self) {
        println!("{}", self.turns.len());
        for turn_moves in &self.turns {
            println!("{}", turn_moves.len());
            for m in turn_moves {
                println!("{} {} {} {}", m.type_, m.i, m.j, m.k);
            }
        }
    }
}

#[fastout]
fn main() {
    let start_time = Instant::now();
    input! {
        r: usize,
        y: [[usize; 10]; r],
    }
    let mut y_arr = [[0; 10]; R];
    for i in 0..r {
        for j in 0..10 {
            y_arr[i][j] = y[i][j];
        }
    }
    let input = Input { y: y_arr };
    solve(start_time, &input);
}

fn apply_moves(
    state: &mut State,
    turns: &mut Vec<Vec<Move>>,
    moves: &[Move],
    hasher: &ZobristHasher,
) {
    apply_moves_state_only(state, moves, hasher);
    turns.push(moves.to_vec());
}

fn apply_moves_state_only(state: &mut State, moves: &[Move], hasher: &ZobristHasher) {
    if moves.is_empty() {
        return;
    }
    for m in moves {
        let k = m.k as usize;
        if m.type_ == 0 {
            let i = m.i as usize;
            let j = m.j as usize;
            let mut chunk = Vec::new();
            for _ in 0..k {
                let p = state.d[i].len() - 1;
                let val = state.d[i].pop().unwrap();
                state.hash ^= hasher.table[0][i][p][val as usize];
                chunk.push(val);
            }
            for val in chunk.into_iter() {
                let p = state.s[j].len();
                state.s[j].push(val);
                state.hash ^= hasher.table[1][j][p][val as usize];
            }
        } else {
            let i = m.i as usize;
            let j = m.j as usize;
            let mut chunk = Vec::new();
            for _ in 0..k {
                let p = state.s[j].len() - 1;
                let val = state.s[j].pop().unwrap();
                state.hash ^= hasher.table[1][j][p][val as usize];
                chunk.push(val);
            }
            for val in chunk.into_iter() {
                let p = state.d[i].len();
                state.d[i].push(val);
                state.hash ^= hasher.table[0][i][p][val as usize];
            }
        }
    }
}

fn return_to_departure(state: &mut State, turns: &mut Vec<Vec<Move>>, hasher: &ZobristHasher) {
    loop {
        let mut plans = Vec::new();
        for j in 0..R {
            if !state.s[j].is_empty() {
                plans.push((j, j, state.s[j].len()));
            }
        }
        if plans.is_empty() {
            break;
        }

        let mut approved = Vec::new();
        for &(j, i, k) in &plans {
            let mut conflict = false;
            for &(aj, ai, _) in &approved {
                if i == ai || j == aj || (i as isize - ai as isize) * (j as isize - aj as isize) < 0
                {
                    conflict = true;
                    break;
                }
            }
            if !conflict {
                approved.push((j, i, k));
            }
        }

        let mut turn_moves = Vec::new();
        for &(j, i, k) in &approved {
            turn_moves.push(Move::new(1, i, j, k));
        }
        apply_moves(state, turns, &turn_moves, hasher);
    }
}

fn final_step(state: &mut State, turns: &mut Vec<Vec<Move>>, hasher: &ZobristHasher) {
    loop {
        let mut plans = Vec::new();
        for p in 0..5 {
            let s_left = 2 * p;
            let s_right = 2 * p + 1;

            let j = if !state.s[s_left].is_empty() {
                s_left
            } else if !state.s[s_right].is_empty() {
                s_right
            } else {
                continue;
            };

            let mut k = 0;
            let mut target_i = None;
            for idx in (0..state.s[j].len()).rev() {
                let v = state.s[j][idx];
                let i = (v / 10) as usize;
                if let Some(ti) = target_i {
                    if i != ti {
                        break;
                    }
                } else {
                    target_i = Some(i);
                }
                k += 1;
            }

            let i = target_i.unwrap();
            let max_k = DEP_CAPACITY - state.d[i].len();
            if k > max_k {
                k = max_k;
            }
            if k > 0 {
                plans.push((j, i, state.s[j].len(), k));
            }
        }

        if plans.is_empty() {
            break;
        }

        plans.sort_by_key(|&(_, _, v, _)| std::cmp::Reverse(v));

        let mut approved = Vec::new();
        for &(j, i, v, k) in &plans {
            let mut conflict = false;
            for &(aj, ai, _, _) in &approved {
                if i == ai || j == aj || (i as isize - ai as isize) * (j as isize - aj as isize) < 0
                {
                    conflict = true;
                    break;
                }
            }
            if !conflict {
                approved.push((j, i, v, k));
            }
        }

        let mut turn_moves = Vec::new();
        for &(j, i, _, k) in &approved {
            turn_moves.push(Move::new(1, i, j, k));
        }
        apply_moves(state, turns, &turn_moves, hasher);
    }
}

fn process_radix_step(
    state: &mut State,
    turns: &mut Vec<Vec<Move>>,
    columns: &[usize],
    bit_idx: usize,
    hasher: &ZobristHasher,
) {
    loop {
        let mut plans = Vec::new();
        for &i in columns {
            if state.d[i].is_empty() {
                continue;
            }

            let mut k = 0;
            let mut target_j = None;
            for idx in (0..state.d[i].len()).rev() {
                let v = state.d[i][idx];
                let target_dep = (v / 10) as usize;
                let p = target_dep / 2;
                let bit = (((v % 10) >> bit_idx) & 1) as usize;
                let j = 2 * p + bit;

                if let Some(tj) = target_j {
                    if j != tj {
                        break;
                    }
                } else {
                    target_j = Some(j);
                }
                k += 1;
            }

            let j = target_j.unwrap();
            let max_k = SID_CAPACITY - state.s[j].len();
            if k > max_k {
                k = max_k;
            }
            if k > 0 {
                plans.push((i, j, state.d[i].len(), k));
            }
        }

        if plans.is_empty() {
            break;
        }

        plans.sort_by_key(|&(_, _, v, _)| std::cmp::Reverse(v));

        let mut approved = Vec::new();
        for &(i, j, v, k) in &plans {
            let mut conflict = false;
            for &(ai, aj, _, _) in &approved {
                if i == ai || j == aj || (i as isize - ai as isize) * (j as isize - aj as isize) < 0
                {
                    conflict = true;
                    break;
                }
            }
            if !conflict {
                approved.push((i, j, v, k));
            }
        }

        let mut turn_moves = Vec::new();
        for &(i, j, _, k) in &approved {
            turn_moves.push(Move::new(0, i, j, k));
        }
        apply_moves(state, turns, &turn_moves, hasher);
    }
}

#[derive(Clone)]
struct BeamNode {
    state: State,
    turn_count: usize,
    phase: usize,
    eval: usize,
}

fn evaluate(state: &State, phase: usize) -> usize {
    let mut total_remaining = 0;
    let mut max_remaining = 0;

    if phase == 0 {
        for i in 0..R {
            let len = state.d[i].len();
            total_remaining += len;
            if len > max_remaining {
                max_remaining = len;
            }
        }
    } else if phase == 1 {
        for j in 0..R {
            let len = state.s[j].len();
            total_remaining += len;
            if len > max_remaining {
                max_remaining = len;
            }
        }
    } else if phase == 2 {
        let cols = [1, 3, 5, 7, 9];
        for &i in &cols {
            let len = state.d[i].len();
            total_remaining += len;
            if len > max_remaining {
                max_remaining = len;
            }
        }
    } else if phase == 3 {
        let cols = [0, 2, 4, 6, 8];
        for &i in &cols {
            let len = state.d[i].len();
            total_remaining += len;
            if len > max_remaining {
                max_remaining = len;
            }
        }
    }
    total_remaining + max_remaining * 5
}

fn get_step1_plans(state: &State) -> Vec<(usize, usize, usize, usize)> {
    let mut plans = Vec::new();
    for i in 0..R {
        if state.d[i].is_empty() {
            continue;
        }

        let mut k = 0;
        let mut target_j = None;
        for idx in (0..state.d[i].len()).rev() {
            let v = state.d[i][idx];
            let target_dep = (v / 10) as usize;
            let bit0 = ((v % 10) % 2) as usize;
            let mut j = if i <= 3 {
                if target_dep <= 4 {
                    0 + bit0
                } else {
                    2 + bit0
                }
            } else if i <= 5 {
                4 + bit0
            } else {
                if target_dep <= 4 {
                    6 + bit0
                } else {
                    8 + bit0
                }
            };

            if state.s[j].len() >= 15 {
                let mut best_j = j;
                let mut min_len = state.s[j].len();
                for p in 0..5 {
                    let cand_j = 2 * p + bit0;
                    if state.s[cand_j].len() < min_len {
                        min_len = state.s[cand_j].len();
                        best_j = cand_j;
                    }
                }
                j = best_j;
            }

            if let Some(tj) = target_j {
                if j != tj {
                    break;
                }
            } else {
                target_j = Some(j);
            }
            k += 1;
        }

        let j = target_j.unwrap();
        let max_k = 15 - state.s[j].len();
        let mut actual_k = k;
        if actual_k > max_k {
            actual_k = max_k;
        }
        if actual_k > 0 {
            plans.push((i, j, state.d[i].len(), actual_k));
        }
    }
    plans
}

fn get_return_plans(state: &State) -> Vec<(usize, usize, usize, usize)> {
    let mut plans = Vec::new();
    for j in 0..R {
        if !state.s[j].is_empty() {
            plans.push((j, j, state.s[j].len(), state.s[j].len()));
        }
    }
    plans
}

fn get_radix_plans(
    state: &State,
    columns: &[usize],
    bit_idx: usize,
) -> Vec<(usize, usize, usize, usize)> {
    let mut plans = Vec::new();
    for &i in columns {
        if state.d[i].is_empty() {
            continue;
        }

        let mut k = 0;
        let mut target_j = None;
        for idx in (0..state.d[i].len()).rev() {
            let v = state.d[i][idx];
            let target_dep = (v / 10) as usize;
            let p = target_dep / 2;
            let bit = (((v % 10) >> bit_idx) & 1) as usize;
            let j = 2 * p + bit;

            if let Some(tj) = target_j {
                if j != tj {
                    break;
                }
            } else {
                target_j = Some(j);
            }
            k += 1;
        }

        let j = target_j.unwrap();
        let max_k = SID_CAPACITY - state.s[j].len();
        let mut actual_k = k;
        if actual_k > max_k {
            actual_k = max_k;
        }
        if actual_k > 0 {
            plans.push((i, j, state.d[i].len(), actual_k));
        }
    }
    plans
}

fn generate_diverse_moves(
    state: &State,
    mut plans: Vec<(usize, usize, usize, usize)>,
    type_: usize,
    check_capacity: bool,
    rng: &mut ChaCha8Rng,
) -> Vec<Vec<Move>> {
    if plans.is_empty() {
        return vec![vec![]];
    }

    let mut candidates = Vec::new();

    plans.sort_by_key(|&(_, _, v, _)| std::cmp::Reverse(v));

    let get_moves = |p: &[(usize, usize, usize, usize)]| {
        let mut turn_moves: Vec<Move> = Vec::new();
        let mut j_incoming = [0; R];
        for &(u, v_target, _, k) in p {
            let i = if type_ == 0 { u } else { v_target };
            let j = if type_ == 0 { v_target } else { u };
            let mut conflict = false;
            for m in &turn_moves {
                let ai = m.i as usize;
                let aj = m.j as usize;
                if i == ai || j == aj || (i as isize - ai as isize) * (j as isize - aj as isize) < 0
                {
                    conflict = true;
                    break;
                }
            }
            if !conflict {
                if check_capacity && type_ == 0 {
                    if state.s[j].len() + j_incoming[j] + k <= 15 {
                        turn_moves.push(Move::new(type_, i, j, k));
                        j_incoming[j] += k;
                    }
                } else {
                    turn_moves.push(Move::new(type_, i, j, k));
                }
            }
        }
        turn_moves
    };

    candidates.push(get_moves(&plans));

    for skip_idx in 0..plans.len().min(3) {
        let mut p = plans.clone();
        p.remove(skip_idx);
        candidates.push(get_moves(&p));
    }

    for _ in 0..5 {
        let mut p = plans.clone();
        p.shuffle(rng);
        candidates.push(get_moves(&p));
    }

    candidates.sort_by_key(|m: &Vec<Move>| m.len());
    candidates.dedup();
    candidates
}

fn expand_single(
    node: &BeamNode,
    rng: &mut ChaCha8Rng,
    hasher: &ZobristHasher,
) -> Vec<(BeamNode, Vec<Move>)> {
    let state = &node.state;
    let mut next_nodes = Vec::new();

    if node.phase == 0 {
        let plans = get_step1_plans(state);
        if plans.is_empty() {
            let mut next_node = node.clone();
            next_node.phase = 1;
            next_node.eval = evaluate(&next_node.state, 1);
            next_nodes.push((next_node, vec![]));
        } else {
            let candidates = generate_diverse_moves(state, plans.clone(), 0, true, rng);
            for moves in candidates {
                if moves.is_empty() {
                    continue;
                }
                let mut next_state = state.clone();
                apply_moves_state_only(&mut next_state, &moves, hasher);
                let eval = evaluate(&next_state, 0);
                next_nodes.push((
                    BeamNode {
                        state: next_state,
                        turn_count: node.turn_count + 1,
                        phase: 0,
                        eval,
                    },
                    moves,
                ));
            }
        }
    } else if node.phase == 1 {
        let plans = get_return_plans(state);
        if plans.is_empty() {
            let mut next_node = node.clone();
            next_node.phase = 2;
            next_node.eval = evaluate(&next_node.state, 2);
            next_nodes.push((next_node, vec![]));
        } else {
            let candidates = generate_diverse_moves(state, plans, 1, false, rng);
            for moves in candidates {
                if moves.is_empty() {
                    continue;
                }
                let mut next_state = state.clone();
                apply_moves_state_only(&mut next_state, &moves, hasher);
                let eval = evaluate(&next_state, 1);
                next_nodes.push((
                    BeamNode {
                        state: next_state,
                        turn_count: node.turn_count + 1,
                        phase: 1,
                        eval,
                    },
                    moves,
                ));
            }
        }
    } else if node.phase == 2 {
        let plans = get_radix_plans(state, &[1, 3, 5, 7, 9], 1);
        if plans.is_empty() {
            let mut next_node = node.clone();
            next_node.phase = 3;
            next_node.eval = evaluate(&next_node.state, 3);
            next_nodes.push((next_node, vec![]));
        } else {
            let candidates = generate_diverse_moves(state, plans, 0, false, rng);
            for moves in candidates {
                if moves.is_empty() {
                    continue;
                }
                let mut next_state = state.clone();
                apply_moves_state_only(&mut next_state, &moves, hasher);
                let eval = evaluate(&next_state, 2);
                next_nodes.push((
                    BeamNode {
                        state: next_state,
                        turn_count: node.turn_count + 1,
                        phase: 2,
                        eval,
                    },
                    moves,
                ));
            }
        }
    } else if node.phase == 3 {
        let plans = get_radix_plans(state, &[0, 2, 4, 6, 8], 1);
        if plans.is_empty() {
            let mut next_node = node.clone();
            next_node.phase = 4;
            next_node.eval = 0;
            next_nodes.push((next_node, vec![]));
        } else {
            let candidates = generate_diverse_moves(state, plans, 0, false, rng);
            for moves in candidates {
                if moves.is_empty() {
                    continue;
                }
                let mut next_state = state.clone();
                apply_moves_state_only(&mut next_state, &moves, hasher);
                let eval = evaluate(&next_state, 3);
                next_nodes.push((
                    BeamNode {
                        state: next_state,
                        turn_count: node.turn_count + 1,
                        phase: 3,
                        eval,
                    },
                    moves,
                ));
            }
        }
    }
    next_nodes
}

fn expand_recursively(
    node: &BeamNode,
    rng: &mut ChaCha8Rng,
    start_time: Instant,
    time_limit_ms: u128,
    hasher: &ZobristHasher,
) -> Vec<(BeamNode, Vec<Move>)> {
    if start_time.elapsed().as_millis() > time_limit_ms {
        return Vec::new();
    }
    let mut result = Vec::new();
    let next_states = expand_single(node, rng, hasher);
    for (next_node, moves) in next_states {
        if start_time.elapsed().as_millis() > time_limit_ms {
            break;
        }
        if moves.is_empty() && next_node.phase < 4 {
            let mut deeper = expand_recursively(&next_node, rng, start_time, time_limit_ms, hasher);
            result.append(&mut deeper);
        } else {
            result.push((next_node, moves));
        }
    }
    result
}

fn run_chokudai_search(
    initial_state: &State,
    start_time: Instant,
    time_limit_ms: u128,
    hasher: &ZobristHasher,
) -> Option<(State, Vec<Vec<Move>>)> {
    let mut rng = ChaCha8Rng::seed_from_u64(42);

    let max_depth = 400;
    let mut queues: Vec<Vec<(BeamNode, Vec<Vec<Move>>)>> = vec![Vec::new(); max_depth];
    let mut visited: HashMap<(u64, usize), usize> = HashMap::new();

    let initial_node = BeamNode {
        state: initial_state.clone(),
        turn_count: 0,
        phase: 0,
        eval: evaluate(initial_state, 0),
    };
    queues[0].push((initial_node, Vec::new()));

    let mut best_completed_node: Option<(BeamNode, Vec<Vec<Move>>)> = None;

    let max_chokudai_width = 3;

    loop {
        if start_time.elapsed().as_millis() > time_limit_ms {
            break;
        }

        let mut expanded_any = false;

        for d in 0..max_depth - 1 {
            if start_time.elapsed().as_millis() > time_limit_ms {
                break;
            }

            queues[d].sort_by_key(|(n, _)| std::cmp::Reverse(n.eval));

            let mut count = 0;
            while let Some((node, path)) = queues[d].pop() {
                if start_time.elapsed().as_millis() > time_limit_ms {
                    break;
                }

                // 枝刈り (古い状態で、より良いターン数で到達済みならスキップ)
                if let Some(&best_turns) = visited.get(&(node.state.hash, node.phase)) {
                    if best_turns <= node.turn_count {
                        continue;
                    }
                }
                visited.insert((node.state.hash, node.phase), node.turn_count);

                count += 1;
                expanded_any = true;

                if node.phase == 4 {
                    if best_completed_node.is_none()
                        || node.turn_count < best_completed_node.as_ref().unwrap().0.turn_count
                    {
                        best_completed_node = Some((node.clone(), path.clone()));
                    }
                    continue;
                }

                let next_states =
                    expand_recursively(&node, &mut rng, start_time, time_limit_ms, hasher);
                for (next_node, moves) in next_states {
                    if start_time.elapsed().as_millis() > time_limit_ms {
                        break;
                    }

                    let mut next_d = next_node.turn_count;
                    
                    if next_node.phase == 4 {
                        let mut next_path = path.clone();
                        if !moves.is_empty() {
                            next_path.push(moves.clone());
                        }
                        if best_completed_node.is_none() || next_d < best_completed_node.as_ref().unwrap().0.turn_count {
                            best_completed_node = Some((next_node.clone(), next_path));
                        }
                    }

                    // 新しい状態のハッシュチェック
                    let mut should_push = true;
                    if let Some(&best_turns) = visited.get(&(next_node.state.hash, next_node.phase)) {
                        if best_turns <= next_d {
                            // 同じ状態でより少ないターン数があればスキップ。ただし、phase 4 に到達したなら既に記録済みなのでスキップして良い
                            should_push = false;
                        }
                    }
                    
                    if should_push && next_node.phase < 4 {
                        let mut next_path = path.clone();
                        if !moves.is_empty() {
                            next_path.push(moves);
                        }
                        if next_d < max_depth {
                            queues[next_d].push((next_node, next_path));
                            
                            // 状態数が増えすぎないように制限（メモリ超過対策）
                            if queues[next_d].len() > 200 {
                                queues[next_d].sort_by_key(|(n, _)| n.eval);
                                queues[next_d].truncate(100);
                            }
                        }
                    }
                }

                if count >= max_chokudai_width {
                    break;
                }
            }
        }

        if !expanded_any {
            break;
        }
    }

    if let Some((best_node, best_path)) = best_completed_node {
        Some((best_node.state, best_path))
    } else {
        None
    }
}

fn solve_greedy(initial_state: &State, hasher: &ZobristHasher) -> Vec<Vec<Move>> {
    let mut state = initial_state.clone();
    let mut turns = Vec::new();

    // Step 1
    loop {
        let plans = get_step1_plans(&state);
        if plans.is_empty() {
            break;
        }

        let mut approved = Vec::new();
        let mut j_incoming = [0; R];
        let mut sorted_plans = plans.clone();
        sorted_plans.sort_by_key(|&(_, _, v, _)| std::cmp::Reverse(v));

        for &(i, j, v, k) in &sorted_plans {
            let mut conflict = false;
            for &(ai, aj, _, _) in &approved {
                if i == ai || j == aj || (i as isize - ai as isize) * (j as isize - aj as isize) < 0
                {
                    conflict = true;
                    break;
                }
            }
            if !conflict {
                if state.s[j].len() + j_incoming[j] + k <= 15 {
                    approved.push((i, j, v, k));
                    j_incoming[j] += k;
                }
            }
        }
        let mut turn_moves = Vec::new();
        for &(i, j, _, k) in &approved {
            turn_moves.push(Move::new(0, i, j, k));
        }
        apply_moves(&mut state, &mut turns, &turn_moves, hasher);
    }

    // Steps 2-4
    for k in 1..=3 {
        return_to_departure(&mut state, &mut turns, hasher);
        process_radix_step(&mut state, &mut turns, &[1, 3, 5, 7, 9], k, hasher);
        process_radix_step(&mut state, &mut turns, &[0, 2, 4, 6, 8], k, hasher);
    }

    final_step(&mut state, &mut turns, hasher);
    turns
}

fn solve(start_time: Instant, input: &Input) {
    let mut rng = ChaCha8Rng::seed_from_u64(42);
    let hasher = ZobristHasher::new(&mut rng);

    let mut initial_state = State {
        d: [FixedLine::new(); R],
        s: [FixedLine::new(); R],
        hash: 0,
    };
    for r in 0..R {
        for c in 0..10 {
            let val = input.y[r][c] as u8;
            initial_state.d[r].push(val);
            initial_state.hash ^= hasher.table[0][r][c][val as usize];
        }
    }

    // 1. フォールバック解
    let mut best_turns = solve_greedy(&initial_state, &hasher);
    eprintln!("Greedy turns: {}", best_turns.len());

    // 2. Chokudai Search
    if let Some((mut search_state, mut search_turns)) =
        run_chokudai_search(&initial_state, start_time, 1800, &hasher)
    {
        if start_time.elapsed().as_millis() > 1800 {
            eprintln!("Chokudai Search exceeded time limit");
        } else {
            eprintln!(
                "Search found a state in {} turns for phase 1-3",
                search_turns.len()
            );
        }

        // 残りをプレイアウト
        for k in 2..=3 {
            return_to_departure(&mut search_state, &mut search_turns, &hasher);
            process_radix_step(
                &mut search_state,
                &mut search_turns,
                &[1, 3, 5, 7, 9],
                k,
                &hasher,
            );
            process_radix_step(
                &mut search_state,
                &mut search_turns,
                &[0, 2, 4, 6, 8],
                k,
                &hasher,
            );
        }
        final_step(&mut search_state, &mut search_turns, &hasher);

        eprintln!("Search total turns: {}", search_turns.len());
        if search_turns.len() < best_turns.len() {
            best_turns = search_turns;
        }
    }

    let out = Output { turns: best_turns };
    out.print();
}

Submission Info

Compile Error

warning: use of deprecated method `rand::Rng::r#gen`: Renamed to `random` to avoid conflict with the new `gen` keyword in Rust 2024.
  --> src/main.rs:71:49
   |
71 |                         table[t][i][p][v] = rng.r#gen();
   |                                                 ^^^^^
   |
   = note: `#[warn(deprecated)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:812:25
    |
812 |                     let mut next_d = next_node.turn_count;
    |                         ----^^^^^^
    |                         |
    |                         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

Judge Result