結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
👑  terry_u16
|
| 提出日時 | 2025-07-26 16:56:36 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,332 ms / 2,000 ms |
| コード長 | 29,273 bytes |
| コンパイル時間 | 13,938 ms |
| コンパイル使用メモリ | 404,632 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,208,718,286 |
| 最終ジャッジ日時 | 2025-07-26 16:57:58 |
| 合計ジャッジ時間 | 81,659 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: associated function `from_entropy` is never used
--> src/main.rs:484:16
|
467 | impl Xoshiro256PlusPlus {
| ----------------------- associated function in this implementation
...
484 | pub fn from_entropy() -> Self {
| ^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: function `thread_rng` is never used
--> src/main.rs:544:12
|
544 | pub fn thread_rng() -> Xoshiro256PlusPlus {
| ^^^^^^^^^^
warning: method `write_if_improve` is never used
--> src/main.rs:981:12
|
915 | impl State {
| ---------- method in this implementation
...
981 | fn write_if_improve(&mut self) -> Result<(), ()> {
| ^^^^^^^^^^^^^^^^
ソースコード
#[allow(dead_code)]
mod grid {
use std::{
fmt::Display,
ops::{Add, AddAssign, Index, IndexMut},
};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct Coord {
row: u8,
col: u8,
}
impl Coord {
pub const fn new(row: usize, col: usize) -> Self {
Self {
row: row as u8,
col: col as u8,
}
}
pub const fn row(&self) -> usize {
self.row as usize
}
pub const fn col(&self) -> usize {
self.col as usize
}
pub fn in_map(&self, size: usize) -> bool {
self.row < size as u8 && self.col < size as u8
}
pub const fn to_index(&self, size: usize) -> CoordIndex {
CoordIndex(self.row as usize * size + self.col as usize)
}
pub const fn dist(&self, other: &Self) -> usize {
Self::dist_1d(self.row, other.row) + Self::dist_1d(self.col, other.col)
}
const fn dist_1d(x0: u8, x1: u8) -> usize {
x0.abs_diff(x1) as usize
}
}
impl Display for Coord {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "({}, {})", self.row, self.col)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct CoordIndex(pub usize);
impl CoordIndex {
pub const fn to_coord(&self, size: usize) -> Coord {
Coord::new(self.0 / size, self.0 % size)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct CoordDiff {
dr: i8,
dc: i8,
}
impl CoordDiff {
pub const fn new(dr: i32, dc: i32) -> Self {
Self {
dr: dr as i8,
dc: dc as i8,
}
}
pub const fn invert(&self) -> Self {
Self {
dr: -self.dr,
dc: -self.dc,
}
}
pub const fn dr(&self) -> i32 {
self.dr as i32
}
pub const fn dc(&self) -> i32 {
self.dc as i32
}
}
impl Display for CoordDiff {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "({}, {})", self.dr, self.dc)
}
}
impl Add<CoordDiff> for Coord {
type Output = Coord;
fn add(self, rhs: CoordDiff) -> Self::Output {
Coord {
row: self.row.wrapping_add(rhs.dr as u8),
col: self.col.wrapping_add(rhs.dc as u8),
}
}
}
impl AddAssign<CoordDiff> for Coord {
fn add_assign(&mut self, rhs: CoordDiff) {
self.row = self.row.wrapping_add(rhs.dr as u8);
self.col = self.col.wrapping_add(rhs.dc as u8);
}
}
pub const ADJACENTS: [CoordDiff; 4] = [
CoordDiff::new(-1, 0),
CoordDiff::new(0, 1),
CoordDiff::new(1, 0),
CoordDiff::new(0, -1),
];
pub const U: usize = 0;
pub const R: usize = 1;
pub const D: usize = 2;
pub const L: usize = 3;
pub const DIRECTIONS: [char; 4] = ['U', 'R', 'D', 'L'];
#[derive(Debug, Clone)]
pub struct Map2d<T> {
size: usize,
map: Vec<T>,
}
impl<T> Map2d<T> {
pub fn new(map: Vec<T>, size: usize) -> Self {
debug_assert!(size * size == map.len());
Self { size, map }
}
pub fn from_fn(mut f: impl FnMut(Coord) -> T, size: usize) -> Self {
let mut map = Vec::with_capacity(size * size);
for row in 0..size {
for col in 0..size {
map.push(f(Coord::new(row, col)));
}
}
Self { size, map }
}
pub fn iter(&self) -> impl Iterator<Item = &T> {
self.map.iter()
}
}
impl<T: Default + Clone> Map2d<T> {
pub fn with_default(size: usize) -> Self {
let map = vec![T::default(); size * size];
Self { size, map }
}
}
impl<T> Index<Coord> for Map2d<T> {
type Output = T;
#[inline]
fn index(&self, coordinate: Coord) -> &Self::Output {
&self.map[coordinate.to_index(self.size).0]
}
}
impl<T> IndexMut<Coord> for Map2d<T> {
#[inline]
fn index_mut(&mut self, coordinate: Coord) -> &mut Self::Output {
&mut self.map[coordinate.to_index(self.size).0]
}
}
impl<T> Index<&Coord> for Map2d<T> {
type Output = T;
#[inline]
fn index(&self, coordinate: &Coord) -> &Self::Output {
&self.map[coordinate.to_index(self.size).0]
}
}
impl<T> IndexMut<&Coord> for Map2d<T> {
#[inline]
fn index_mut(&mut self, coordinate: &Coord) -> &mut Self::Output {
&mut self.map[coordinate.to_index(self.size).0]
}
}
impl<T> Index<usize> for Map2d<T> {
type Output = [T];
#[inline]
fn index(&self, row: usize) -> &Self::Output {
let begin = row * self.size;
let end = begin + self.size;
&self.map[begin..end]
}
}
impl<T> IndexMut<usize> for Map2d<T> {
#[inline]
fn index_mut(&mut self, row: usize) -> &mut Self::Output {
let begin = row * self.size;
let end = begin + self.size;
&mut self.map[begin..end]
}
}
impl<T> Index<CoordIndex> for Map2d<T> {
type Output = T;
#[inline]
fn index(&self, index: CoordIndex) -> &Self::Output {
&self.map[index.0]
}
}
impl<T> IndexMut<CoordIndex> for Map2d<T> {
#[inline]
fn index_mut(&mut self, index: CoordIndex) -> &mut Self::Output {
&mut self.map[index.0]
}
}
#[derive(Debug, Clone)]
pub struct ConstMap2d<T, const N: usize> {
map: Vec<T>,
}
impl<T, const N: usize> ConstMap2d<T, N> {
pub fn new(map: Vec<T>) -> Self {
assert_eq!(map.len(), N * N);
Self { map }
}
pub fn from_fn(mut f: impl FnMut(Coord) -> T) -> Self {
let mut map = Vec::with_capacity(N * N);
for row in 0..N {
for col in 0..N {
map.push(f(Coord::new(row, col)));
}
}
Self { map }
}
}
impl<T: Default + Clone, const N: usize> ConstMap2d<T, N> {
pub fn with_default() -> Self {
let map = vec![T::default(); N * N];
Self { map }
}
}
impl<T, const N: usize> Index<Coord> for ConstMap2d<T, N> {
type Output = T;
#[inline]
fn index(&self, coordinate: Coord) -> &Self::Output {
&self.map[coordinate.to_index(N).0]
}
}
impl<T, const N: usize> IndexMut<Coord> for ConstMap2d<T, N> {
#[inline]
fn index_mut(&mut self, coordinate: Coord) -> &mut Self::Output {
&mut self.map[coordinate.to_index(N).0]
}
}
impl<T, const N: usize> Index<&Coord> for ConstMap2d<T, N> {
type Output = T;
#[inline]
fn index(&self, coordinate: &Coord) -> &Self::Output {
&self.map[coordinate.to_index(N).0]
}
}
impl<T, const N: usize> IndexMut<&Coord> for ConstMap2d<T, N> {
#[inline]
fn index_mut(&mut self, coordinate: &Coord) -> &mut Self::Output {
&mut self.map[coordinate.to_index(N).0]
}
}
impl<T, const N: usize> Index<usize> for ConstMap2d<T, N> {
type Output = [T];
#[inline]
fn index(&self, row: usize) -> &Self::Output {
let begin = row * N;
let end = begin + N;
&self.map[begin..end]
}
}
impl<T, const N: usize> IndexMut<usize> for ConstMap2d<T, N> {
#[inline]
fn index_mut(&mut self, row: usize) -> &mut Self::Output {
let begin = row * N;
let end = begin + N;
&mut self.map[begin..end]
}
}
impl<T, const N: usize> Index<CoordIndex> for ConstMap2d<T, N> {
type Output = T;
#[inline]
fn index(&self, index: CoordIndex) -> &Self::Output {
&self.map[index.0]
}
}
impl<T, const N: usize> IndexMut<CoordIndex> for ConstMap2d<T, N> {
#[inline]
fn index_mut(&mut self, index: CoordIndex) -> &mut Self::Output {
&mut self.map[index.0]
}
}
#[cfg(test)]
mod test {
use super::{ConstMap2d, Coord, CoordDiff, Map2d};
#[test]
fn coord_add() {
let c = Coord::new(2, 4);
let d = CoordDiff::new(-3, 5);
let actual = c + d;
let expected = Coord::new(!0, 9);
assert_eq!(expected, actual);
}
#[test]
fn coord_add_assign() {
let mut c = Coord::new(2, 4);
let d = CoordDiff::new(-3, 5);
c += d;
let expected = Coord::new(!0, 9);
assert_eq!(expected, c);
}
#[test]
fn map_new() {
let map = Map2d::new(vec![0, 1, 2, 3], 2);
let actual = map[Coord::new(1, 0)];
let expected = 2;
assert_eq!(expected, actual);
}
#[test]
fn map_default() {
let map = Map2d::with_default(2);
let actual = map[Coord::new(1, 0)];
let expected = 0;
assert_eq!(expected, actual);
}
#[test]
fn const_map_new() {
let map = ConstMap2d::<_, 2>::new(vec![0, 1, 2, 3]);
let actual = map[Coord::new(1, 0)];
let expected = 2;
assert_eq!(expected, actual);
}
#[test]
fn const_map_default() {
let map = ConstMap2d::<_, 2>::with_default();
let actual = map[Coord::new(1, 0)];
let expected = 0;
assert_eq!(expected, actual);
}
}
}
mod problem {
use std::fmt::Display;
use crate::grid::Map2d;
use proconio::input;
#[derive(Debug, Clone)]
pub struct Input {
pub map: Map2d<u32>,
}
impl Input {
pub const MAP_SIZE: usize = 10;
pub const MAX_TURN: usize = 1000;
pub fn read() -> Self {
input! {
n: usize,
_t: usize,
map: [u32; n * n]
}
let map = Map2d::new(map, Self::MAP_SIZE);
Self { map }
}
}
#[derive(Debug, Clone)]
pub struct Output {
pub actions: Vec<Action>,
pub score: u32,
}
impl Output {
pub fn new(actions: Vec<Action>, score: u32) -> Self {
Self { actions, score }
}
}
impl Display for Output {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
for action in &self.actions {
writeln!(f, "{}", action)?;
}
Ok(())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Action {
Up,
Right,
Down,
Left,
Write,
Copy,
}
impl Display for Action {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Action::Up => write!(f, "U"),
Action::Right => write!(f, "R"),
Action::Down => write!(f, "D"),
Action::Left => write!(f, "L"),
Action::Write => write!(f, "W"),
Action::Copy => write!(f, "C"),
}
}
}
}
mod rand {
pub struct Xoshiro256PlusPlus {
state: [u64; 4],
}
impl Xoshiro256PlusPlus {
pub fn new(seed: u64) -> Self {
let mut rng = Self { state: [0; 4] };
// シードから初期状態を生成
rng.state[0] = seed;
rng.state[1] = seed.wrapping_mul(0x9e3779b97f4a7c15);
rng.state[2] = seed.wrapping_mul(0xbf58476d1ce4e5b9);
rng.state[3] = seed.wrapping_mul(0x94d049bb133111eb);
// 初期化のために数回回す
for _ in 0..16 {
rng.next();
}
rng
}
pub fn from_entropy() -> Self {
// 簡易的なエントロピー生成（実際の環境では改善が必要）
let seed = std::ptr::null::<u8>() as usize as u64;
Self::new(seed)
}
pub fn next(&mut self) -> u64 {
let result = self.state[0]
.wrapping_add(self.state[3])
.rotate_left(23)
.wrapping_add(self.state[0]);
let t = self.state[1] << 17;
self.state[2] ^= self.state[0];
self.state[3] ^= self.state[1];
self.state[1] ^= self.state[2];
self.state[0] ^= self.state[3];
self.state[2] ^= t;
self.state[3] = self.state[3].rotate_left(45);
result
}
pub fn gen_range(&mut self, range: std::ops::Range<usize>) -> usize {
let range_size = range.end - range.start;
if range_size == 0 {
return range.start;
}
let rand_val = self.next() as usize;
range.start + (rand_val % range_size)
}
pub fn gen<T>(&mut self) -> T
where
T: FromRandom,
{
T::from_random(self)
}
}
pub trait FromRandom {
fn from_random(rng: &mut Xoshiro256PlusPlus) -> Self;
}
impl FromRandom for f64 {
fn from_random(rng: &mut Xoshiro256PlusPlus) -> Self {
let val = rng.next();
(val >> 11) as f64 * (1.0 / (1u64 << 53) as f64)
}
}
impl FromRandom for bool {
fn from_random(rng: &mut Xoshiro256PlusPlus) -> Self {
rng.next() & 1 == 1
}
}
pub fn thread_rng() -> Xoshiro256PlusPlus {
Xoshiro256PlusPlus::from_entropy()
}
}
mod solver {
mod tsp {
use crate::{grid::Coord, rand::Xoshiro256PlusPlus, util::ChangeMinMax as _};
pub(super) fn solve(targets: &[Coord]) -> Vec<Coord> {
let state = State::new(targets.to_vec());
let state = annealing(state, 0.05);
state.order
}
fn annealing(initial_solution: State, duration: f64) -> State {
let mut solution = initial_solution;
let mut best_solution = solution.clone();
let mut current_score = solution.dist_sum;
let mut best_score = current_score;
let init_score = current_score;
let mut all_iter = 0;
let mut valid_iter = 0;
let mut accepted_count = 0;
let mut update_count = 0;
let mut rng = Xoshiro256PlusPlus::new(42);
let duration_inv = 1.0 / duration;
let since = std::time::Instant::now();
let temp0 = 1e1;
let temp1 = 1e-1;
let mut inv_temp = 1.0 / temp0;
loop {
all_iter += 1;
if (all_iter & ((1 << 4) - 1)) == 0 {
let time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv;
let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time);
inv_temp = 1.0 / temp;
if time >= 1.0 {
break;
}
}
// 変形
let (l, r) = loop {
let mut l = rng.gen_range(1..solution.order.len());
let mut r = rng.gen_range(1..solution.order.len());
if l != r {
if l > r {
std::mem::swap(&mut l, &mut r);
}
break (l, r);
}
};
let c00 = solution.order[l - 1];
let c01 = solution.order[l];
let c10 = solution.order[r - 1];
let c11 = solution.order[r];
let d00 = c00.dist(&c01);
let d01 = c00.dist(&c10);
let d10 = c01.dist(&c11);
let d11 = c10.dist(&c11);
// スコア計算
let score_diff = (d01 + d10) as isize - (d00 + d11) as isize;
if score_diff <= 0 || rng.gen::<f64>() < f64::exp(-score_diff as f64 * inv_temp) {
// 解の更新
let new_score = current_score.wrapping_add_signed(score_diff);
solution.order[l..r].reverse();
solution.dist_sum = new_score;
current_score = new_score;
accepted_count += 1;
if best_score.change_min(current_score) {
best_solution = solution.clone();
update_count += 1;
}
}
valid_iter += 1;
}
eprintln!("===== annealing =====");
eprintln!("init score : {}", init_score);
eprintln!("score : {}", best_score);
eprintln!("all iter : {}", all_iter);
eprintln!("valid iter : {}", valid_iter);
eprintln!("accepted : {}", accepted_count);
eprintln!("updated : {}", update_count);
eprintln!("");
best_solution
}
#[derive(Debug, Clone)]
struct State {
order: Vec<Coord>,
dist_sum: usize,
}
impl State {
fn new(order: Vec<Coord>) -> Self {
let dist_sum = order.windows(2).map(|w| w[0].dist(&w[1])).sum::<usize>();
Self { order, dist_sum }
}
}
}
use std::usize;
use crate::{
grid::{Coord, Map2d, ADJACENTS, D, L, R, U},
problem::{Action, Input, Output},
util::ChangeMinMax,
};
pub(super) fn solve(input: &Input) -> Output {
let mut best_output = Output::new(vec![], 0);
for base_cnt in 5..=8 {
let output = solve_once(input, base_cnt);
if output.score > best_output.score {
best_output = output;
}
eprintln!("base_cnt: {}, score: {}", base_cnt, best_output.score);
}
best_output
}
pub(super) fn solve_once(input: &Input, base_cnt: usize) -> Output {
let mut state = State::new(input);
let bases = init_base_positions(input, base_cnt);
create_base(&mut state, &bases).unwrap();
let clean_up_turn = calc_clean_up_turn(state.clone(), &bases).unwrap();
let turn_limit = Input::MAX_TURN - clean_up_turn - 5;
for target_digit in (0..20).rev() {
if state.turn >= turn_limit - 5 {
break;
}
eprintln!("target_digit: {}", target_digit);
eprintln!("{:0>20b}", state.s);
state.print_map();
match process_digit(&mut state, target_digit, turn_limit, &bases) {
Ok(()) => {}
Err(()) => break,
}
}
_ = clean_up(&mut state, &bases);
eprintln!("turn: {}", state.turn);
eprintln!("score: {}", state.score);
Output::new(state.actions, state.score)
}
fn init_base_positions(input: &Input, base_cnt: usize) -> Vec<Coord> {
let mut base_positions = vec![];
let mut bases = vec![];
'main: for d in (20 - base_cnt..20).rev() {
for row in 0..5 {
for col in 0..3 {
let c = Coord::new(row, col);
if base_positions.contains(&c) {
continue;
}
let mut xor = input.map[c];
for &b in bases.iter() {
xor = xor.min(xor ^ b);
}
if xor & (1 << d) != 0 {
eprintln!("{:0>20b} at {:?}", xor, c);
base_positions.push(c);
bases.push(xor);
continue 'main;
}
}
}
}
base_positions
}
fn create_base(state: &mut State, bases: &[Coord]) -> Result<(), ()> {
for i in 1..bases.len() {
state.move_to(bases[i])?;
state.apply(Action::Copy)?;
state.apply(Action::Write)?;
for j in 0..i {
if state.s > state.s ^ state.map[bases[j]] {
state.move_to(bases[j])?;
state.apply(Action::Copy)?;
}
}
state.move_to(bases[i])?;
state.apply(Action::Write)?;
state.apply(Action::Copy)?;
}
Ok(())
}
fn process_digit(
state: &mut State,
target_digit: u32,
turn_limit: usize,
bases: &[Coord],
) -> Result<(), ()> {
let mut best_position = None;
let mut best_dist = usize::MAX;
for &c in bases.iter() {
let xor = state.s ^ state.map[c];
let masked = xor & (!0 << target_digit);
if masked == (1 << target_digit) && best_dist.change_min(c.dist(&state.position)) {
best_position = Some(c);
}
}
let Some(base) = best_position else {
// 見つからないパターン
eprintln!("No target found for digit {}", target_digit);
return Ok(());
};
let mut targets = vec![base];
for row in 0..Input::MAP_SIZE {
for col in 0..Input::MAP_SIZE {
let c = Coord::new(row, col);
if !bases.contains(&c) && state.map[c] < state.map[c] ^ state.map[base] {
targets.push(c);
}
}
}
targets.push(base);
let targets = tsp::solve(&targets);
state.move_to(base)?;
state.apply(Action::Copy)?;
for &c in targets[1..targets.len() - 1].iter() {
if state.turn + state.position.dist(&Coord::new(0, 0)) >= turn_limit {
break;
}
state.move_to(c)?;
state.apply(Action::Write)?;
}
state.move_to(base)?;
state.apply(Action::Copy)?;
Ok(())
}
fn calc_clean_up_turn(mut state: State, targets: &[Coord]) -> Result<usize, ()> {
let init_turn = state.turn;
let mut targets = targets.to_vec();
targets.sort_by_key(|c| state.map[*c]);
state.position = targets[0];
for i in 0..targets.len() {
let mut best_flag = None;
let mut best_score = state.map[targets[i]];
for flag in 0..1 << targets.len() {
let mut xor = state.s;
for j in 0..targets.len() {
if (flag >> j) & 1 == 1 {
xor ^= state.map[targets[j]];
}
}
if best_score.change_max(xor ^ state.map[targets[i]]) {
best_flag = Some(flag);
}
}
if let Some(flag) = best_flag {
for j in 0..targets.len() {
if (flag >> j) & 1 == 1 {
state.move_to(targets[j])?;
state.apply(Action::Copy)?;
}
}
state.move_to(targets[i])?;
state.apply(Action::Write)?;
};
}
Ok(state.turn - init_turn)
}
fn clean_up(state: &mut State, targets: &[Coord]) -> Result<(), ()> {
let mut targets = targets.to_vec();
targets.sort_by_key(|c| state.map[*c]);
for i in 0..targets.len() {
let mut best_flag = None;
let mut best_score = state.map[targets[i]];
for flag in 0..1 << targets.len() {
let mut xor = state.s;
for j in 0..targets.len() {
if (flag >> j) & 1 == 1 {
xor ^= state.map[targets[j]];
}
}
if best_score.change_max(xor ^ state.map[targets[i]]) {
best_flag = Some(flag);
}
}
if let Some(flag) = best_flag {
for j in 0..targets.len() {
if (flag >> j) & 1 == 1 {
state.move_to(targets[j])?;
state.apply(Action::Copy)?;
}
}
state.move_to(targets[i])?;
state.apply(Action::Write)?;
};
}
Ok(())
}
#[derive(Debug, Clone)]
struct State {
map: Map2d<u32>,
score: u32,
s: u32,
turn: usize,
position: Coord,
actions: Vec<Action>,
}
impl State {
fn new(input: &Input) -> Self {
let map = input.map.clone();
let position = Coord::new(0, 0);
let score = map.iter().sum();
Self {
map,
score,
s: 0,
turn: 0,
position,
actions: vec![],
}
}
fn apply(&mut self, action: Action) -> Result<(), ()> {
if self.turn >= Input::MAX_TURN {
return Err(());
}
self.turn += 1;
self.actions.push(action);
match action {
Action::Up => self.position += ADJACENTS[U],
Action::Right => self.position += ADJACENTS[R],
Action::Down => self.position += ADJACENTS[D],
Action::Left => self.position += ADJACENTS[L],
Action::Write => {
self.score -= self.map[self.position];
self.map[self.position] ^= self.s;
self.score += self.map[self.position];
}
Action::Copy => self.s ^= self.map[self.position],
}
Ok(())
}
fn move_to(&mut self, target: Coord) -> Result<(), ()> {
let mut actions = vec![];
while self.position.row() > target.row() {
actions.push(Action::Up);
self.apply(Action::Up)?;
}
while self.position.col() < target.col() {
actions.push(Action::Right);
self.apply(Action::Right)?;
}
while self.position.row() < target.row() {
actions.push(Action::Down);
self.apply(Action::Down)?;
}
while self.position.col() > target.col() {
actions.push(Action::Left);
self.apply(Action::Left)?;
}
Ok(())
}
fn write_if_improve(&mut self) -> Result<(), ()> {
let v = self.map[self.position];
if v < v ^ self.s {
self.apply(Action::Write)?;
}
Ok(())
}
fn print_map(&self) {
for row in 0..Input::MAP_SIZE {
for col in 0..Input::MAP_SIZE {
eprint!("{:0>20b} ", self.map[Coord::new(row, col)]);
}
eprintln!();
}
}
}
}
#[allow(dead_code)]
mod util {
//! よく使われるユーティリティ関数をまとめたモジュール
/// 最小値と最大値を更新するトレイト
///
/// # Examples
///
/// ```
/// use cp_lib_rs::util::ChangeMinMax;
///
/// let mut x = 10;
/// assert!(x.change_min(3));
/// assert_eq!(x, 3);
/// ```
#[allow(dead_code)]
pub trait ChangeMinMax {
fn change_min(&mut self, v: Self) -> bool;
fn change_max(&mut self, v: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn change_min(&mut self, v: T) -> bool {
*self > v && {
*self = v;
true
}
}
fn change_max(&mut self, v: T) -> bool {
*self < v && {
*self = v;
true
}
}
}
/// 多次元配列を作成する
///
/// # Examples
///
/// ```
/// use cp_lib_rs::mat;
///
/// let a = mat![0; 4; 3];
/// assert_eq!(a, vec![vec![0; 3]; 4]);
/// ```
#[macro_export]
macro_rules! mat {
($($e:expr),*) => { vec![$($e),*] };
($($e:expr,)*) => { vec![$($e),*] };
($e:expr; $d:expr) => { vec![$e; $d] };
($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}
}
fn main() {
let input = problem::Input::read();
let output = solver::solve(&input);
println!("{}", output);
}