結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 tomerun
|
| 提出日時 | 2025-07-26 16:54:33 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,932 ms / 2,000 ms |
| コード長 | 17,302 bytes |
| コンパイル時間 | 13,077 ms |
| コンパイル使用メモリ | 398,588 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,213,860,654 |
| 最終ジャッジ日時 | 2025-07-26 16:56:26 |
| 合計ジャッジ時間 | 112,070 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(non_snake_case)]
use std::env;
use std::io::{self, BufRead, BufReader, Read, Stdin};
use std::iter;
use std::mem;
use std::str::FromStr;
use std::string::String;
use std::time;
const TIMELIMIT: u64 = 1850;
const INF: usize = 1 << 28;
const N: usize = 10;
const T: usize = 1000;
const DY: [usize; 4] = [!0, 0, 1, 0];
const DX: [usize; 4] = [0, 1, 0, !0];
#[derive(Debug)]
pub struct Scanner<R> {
reader: BufReader<R>,
}
fn scanner() -> Scanner<Stdin> {
Scanner::new(io::stdin())
}
impl<R: io::Read> Scanner<R> {
pub fn new(read: R) -> Scanner<R> {
Scanner {
reader: BufReader::new(read),
}
}
pub fn next_str(&mut self) -> Option<String> {
let mut buf = [0; 1];
let size = self.reader.read(&mut buf).unwrap();
if size == 0 {
None
} else {
self.skip_whitespace(&mut buf)?;
let mut v = vec![buf[0]];
loop {
let size = self.reader.read(&mut buf).unwrap();
if size == 0 || buf[0].is_ascii_whitespace() {
break;
}
v.push(buf[0]);
}
Some(String::from_utf8(v).unwrap())
}
}
pub fn next_line(&mut self) -> String {
let mut line = String::new();
self.reader.read_line(&mut line).unwrap();
if let Some(s) = line.strip_suffix("\n") {
s.to_string()
} else {
line
}
}
pub fn vec<S: FromStr>(&mut self, size: i32) -> Vec<S> {
let mut v: Vec<S> = vec![];
for _ in 0..size {
let token = self.next_str().unwrap();
v.push(S::from_str(&token).ok().unwrap());
}
v
}
pub fn next_as<S: FromStr>(&mut self) -> Option<S> {
let s = self.next_str()?;
S::from_str(&s).ok()
}
pub fn str(&mut self) -> String {
self.next_str().unwrap()
}
pub fn i32(&mut self) -> i32 {
self.next_as::<i32>().unwrap()
}
pub fn u32(&mut self) -> u32 {
self.next_as::<u32>().unwrap()
}
pub fn i64(&mut self) -> i64 {
self.next_as::<i64>().unwrap()
}
pub fn u64(&mut self) -> u64 {
self.next_as::<u64>().unwrap()
}
pub fn usize(&mut self) -> usize {
self.next_as::<usize>().unwrap()
}
fn skip_whitespace(&mut self, mut buf: &mut [u8]) -> Option<u8> {
loop {
if !buf[0].is_ascii_whitespace() {
return Some(buf[0]);
}
let size = self.reader.read(&mut buf).unwrap();
if size == 0 {
return None;
}
}
}
}
struct XorShift32 {
state: u32,
}
impl XorShift32 {
fn from_seed(seed: u32) -> Self {
let initial_state = if seed == 0 { 1 } else { seed };
XorShift32 { state: initial_state }
}
fn next_u32(&mut self) -> u32 {
let mut x = self.state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
self.state = x;
x
}
fn next_f64(&mut self) -> f64 {
self.next_u32() as f64 / (u32::MAX as f64 + 1.0)
}
}
#[derive(Debug)]
struct Timer {
start_time: time::Instant,
limit: time::Instant,
before_time: Option<time::Instant>,
worst_time: time::Duration,
}
impl Timer {
fn new(tl: u64) -> Timer {
let start_time = time::Instant::now();
Timer {
start_time,
limit: start_time + time::Duration::from_millis(tl),
before_time: None,
worst_time: time::Duration::from_millis(0),
}
}
fn elapsed(&self) -> u64 {
self.start_time.elapsed().as_millis() as u64
}
fn checkpoint(&mut self) {
if let Some(before_time) = self.before_time {
let elapsed = before_time.elapsed();
self.worst_time = self.worst_time.max(elapsed);
}
self.before_time = Some(time::Instant::now());
}
fn tl(&self) -> u64 {
(self.limit - self.start_time).as_millis() as u64
}
fn tl_exceeded(&self) -> bool {
self.limit < time::Instant::now()
}
fn should_stop(&self) -> bool {
self.limit < time::Instant::now() + self.worst_time
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pos {
y: usize,
x: usize,
}
impl Pos {
fn new(y: usize, x: usize) -> Pos {
Pos { y, x }
}
fn dist(self, other: Pos) -> i32 {
(self.y as i32 - other.y as i32).abs() + (self.x as i32 - other.x as i32).abs()
}
}
#[derive(Debug, Clone, Copy)]
enum Action {
Up,
Right,
Down,
Left,
Write,
Copy,
}
#[derive(Debug, Clone)]
struct Input {
a: Vec<Vec<u32>>,
}
impl Input {
fn new() -> Input {
let mut sc = scanner();
let _ = sc.usize();
let _ = sc.usize();
let mut a = vec![];
for _ in 0..N {
let mut row = vec![];
for _ in 0..N {
row.push(sc.u32());
}
a.push(row);
}
Input { a }
}
}
#[derive(Debug, Clone)]
struct Result {
actions: Vec<Action>,
score: i64,
}
impl Result {
fn new(actions: Vec<Action>, score: i64) -> Result {
Result { actions, score }
}
fn new_empty() -> Result {
Result {
actions: vec![],
score: -1,
}
}
fn output(&self) {
for &a in &self.actions {
match a {
Action::Up => println!("U"),
Action::Right => println!("R"),
Action::Down => println!("D"),
Action::Left => println!("L"),
Action::Write => println!("W"),
Action::Copy => println!("C"),
}
}
}
}
struct Solver {
input: Input,
timer: Timer,
rng: XorShift32,
}
impl Solver {
fn new(input: Input) -> Solver {
let tl = env::var("TL").map_or(TIMELIMIT, |v| v.parse().unwrap());
let timer = Timer::new(tl);
let rng = XorShift32::from_seed(2);
Solver { input, timer, rng }
}
fn solve(&mut self, tl: u64) -> Result {
let mut best_res = self.solve_single();
eprintln!("score:{:?} turn:{:?}", best_res.score, -1);
let mut turn = 0;
loop {
if self.timer.elapsed() > tl {
eprintln!("solve_single turn:{:?}", turn);
break;
}
let res = self.solve_single();
if res.score > best_res.score {
eprintln!("score:{:?} turn:{:?}", res.score, turn,);
best_res = res;
}
turn += 1;
}
best_res
}
fn move_to(&mut self, cy: &mut usize, cx: &mut usize, ny: usize, nx: usize, acts: &mut Vec<Action>) {
while *cy < ny {
acts.push(Action::Down);
*cy += 1;
}
while *cy > ny {
acts.push(Action::Up);
*cy -= 1;
}
while *cx < nx {
acts.push(Action::Right);
*cx += 1;
}
while *cx > nx {
acts.push(Action::Left);
*cx -= 1;
}
}
fn tsp(&mut self, cy: usize, cx: usize, pos: &Vec<Pos>) -> Vec<Pos> {
if pos.len() < 10 {
let mut dp = vec![vec![INF; 1 << pos.len()]; pos.len()];
let mut prev = vec![vec![INF; 1 << pos.len()]; pos.len()];
for i in 0..pos.len() {
dp[i][1 << i] = pos[i].dist(Pos::new(cy, cx)) as usize;
}
for i in 0..(1 << pos.len()) {
let mut bit: usize = i;
while bit > 0 {
let cur = bit.trailing_zeros() as usize;
for j in 0..pos.len() {
if (i & (1 << j)) != 0 {
continue;
}
let nv = dp[cur][i] + pos[cur].dist(pos[j]) as usize;
if nv < dp[j][i | (1 << j)] {
dp[j][i | (1 << j)] = nv;
prev[j][i | (1 << j)] = cur;
}
}
bit &= bit - 1;
}
}
let mut min_v = INF;
let mut min_i = 0;
for i in 0..pos.len() {
if dp[dp.len() - 1][i] < min_v {
min_v = dp[dp.len() - 1][i];
min_i = i;
}
}
let mut path = vec![pos[min_i]];
let mut bits = (1 << pos.len()) - 1;
loop {
let ni = prev[min_i][bits];
if ni == INF {
break;
}
path.push(pos[ni]);
bits ^= 1 << min_i;
min_i = ni;
}
path.reverse();
return path;
}
let mut order = pos.clone();
for i in 0..order.len() - 1 {
let pos = self.rng.next_u32() as usize % (order.len() - i) + i;
order.swap(i, pos);
}
for turn in 0..100000 {
let mut p0 = self.rng.next_u32() as usize % order.len();
let mut p1 = self.rng.next_u32() as usize % (order.len() - 1);
if p1 >= p0 {
p1 += 1;
} else {
mem::swap(&mut p0, &mut p1);
}
let mut diff = 0;
if p0 == 0 {
diff -= (order[p0].y as i32 - cy as i32).abs() + (order[p0].x as i32 - cx as i32).abs();
diff += (order[p1].y as i32 - cy as i32).abs() + (order[p1].x as i32 - cx as i32).abs();
} else {
diff -= order[p0].dist(order[p0 - 1]);
diff += order[p1].dist(order[p0 - 1]);
}
if p1 < pos.len() - 1 {
diff -= order[p1].dist(order[p1 + 1]);
diff += order[p0].dist(order[p1 + 1]);
} else {
diff -= (order[p1].y as i32 - cy as i32).abs() + (order[p1].x as i32 - cx as i32).abs();
diff += (order[p0].y as i32 - cy as i32).abs() + (order[p0].x as i32 - cx as i32).abs();
}
if diff <= 0 || self.rng.next_f64() < (-diff as f64 * turn as f64 * 0.0001).exp() {
if let Some(slice) = order.get_mut(p0..=p1) {
slice.reverse();
}
}
}
order
}
fn select_base(&mut self) -> Vec<Pos> {
let mut a = self.input.a.clone();
let mut base_pos = vec![];
let mut best_score = 0;
let mut best_base_pos = vec![];
for _ in 0..5000 {
for i in 0..N {
a[i].copy_from_slice(self.input.a[i].as_slice());
}
let mut cy = 0;
let mut cx = 0;
base_pos.clear();
for bi in (13..=19).rev() {
// let mut min_d = N as i32 * 2;
let mut cand_pos = vec![];
for y in 0..N {
for x in 0..N {
let v = a[y][x];
if (v & (1 << bi)) != 0 && v & (0xFFFFE << bi) == 0 {
let d = (y as i32 - cy as i32).abs() + (x as i32 - cx as i32).abs();
if bi == 19 || d < 7 {
cand_pos.push(Pos::new(y, x));
}
// if d < min_d {
// min_d = d;
// cand_pos.clear();
// cand_pos.push(Pos::new(y, x));
// } else if d <= min_d + 1 {
// cand_pos.push(Pos::new(y, x));
// }
}
}
}
let target = cand_pos[self.rng.next_u32() as usize % cand_pos.len()];
base_pos.push(target);
cy = target.y;
cx = target.x;
for y in 0..N {
for x in 0..N {
if (y != cy || x != cx) && (a[y][x] & (1 << bi)) != 0 {
a[y][x] ^= a[cy][cx];
}
}
}
}
let mut s = 0;
let mut lows = vec![];
for p in base_pos.iter() {
s ^= a[p.y][p.x];
lows.push(a[p.y][p.x] & 0x1FFF);
}
let all_lows = lows[0] ^ lows[1] ^ lows[2] ^ lows[3] ^ lows[4] ^ lows[5] ^ lows[6];
let mut score = 0;
for y in 0..N {
for x in 0..N {
if (a[y][x] & 0xFE000) == 0 {
score += a[y][x] ^ s;
}
}
}
score += all_lows * 2;
for i in 2..=6 {
score += (a[base_pos[i].y][base_pos[i].x] ^ all_lows) & 0x1FFF;
}
if score > best_score {
// eprintln!("tmp_score:{:?}", score);
best_score = score;
best_base_pos = base_pos.clone();
}
}
best_base_pos
}
fn solve_single(&mut self) -> Result {
let mut cy = 0;
let mut cx = 0;
let mut acts = vec![];
let mut a = self.input.a.clone();
let mut s = 0;
let base_pos = self.select_base();
let mut is_base = vec![vec![false; N]; N];
for p in &base_pos {
is_base[p.y][p.x] = true;
}
for bi in (13..=19).rev() {
let target = base_pos[19 - bi];
self.move_to(&mut cy, &mut cx, target.y, target.x, &mut acts);
s ^= a[cy][cx];
acts.push(Action::Copy);
if acts.len() >= T {
break;
}
let mut pos = vec![];
for y in 0..N {
for x in 0..N {
if y == cy && x == cx {
continue;
}
if is_base[y][x] ^ ((a[y][x] & (1 << bi)) == 0) {
pos.push(Pos::new(y, x));
}
}
}
let order = self.tsp(cy, cx, &pos);
for p in order {
self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
if acts.len() >= T {
break;
}
a[p.y][p.x] ^= s;
acts.push(Action::Write);
}
self.move_to(&mut cy, &mut cx, target.y, target.x, &mut acts);
s ^= a[cy][cx];
acts.push(Action::Copy);
if acts.len() >= T {
break;
}
}
// eprintln!("acts_len after prepare:{:?}", acts.len());
for p in base_pos.iter().rev() {
self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
s ^= a[cy][cx];
acts.push(Action::Copy);
}
// self.debug_print(s, &a);
let order = self.tsp(cy, cx, &base_pos[1..].to_vec());
for p in order {
self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
if acts.len() >= T {
break;
}
a[p.y][p.x] ^= s;
acts.push(Action::Write);
}
self.move_to(&mut cy, &mut cx, base_pos[0].y, base_pos[0].x, &mut acts);
s ^= a[cy][cx];
acts.push(Action::Copy);
a[cy][cx] ^= s;
acts.push(Action::Write);
eprintln!("acts_len:{:?}", acts.len());
if acts.len() > T {
return Result::new_empty();
}
let order = self.tsp(cy, cx, &base_pos[2..6].to_vec());
for p in order {
self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
s ^= a[cy][cx];
acts.push(Action::Copy);
if acts.len() == T {
break;
}
}
self.move_to(&mut cy, &mut cx, base_pos[1].y, base_pos[1].x, &mut acts);
// self.debug_print(s, &a);
if acts.len() < T {
a[cy][cx] ^= s;
acts.push(Action::Write);
}
if acts.len() > T {
acts.truncate(T);
}
let score = a.iter().flatten().map(|&v| v as i64).sum::<i64>();
// self.debug_print(s, &a);
eprintln!("score:{:?}", score);
Result::new(acts, score)
}
fn debug_print(&self, s: u32, a: &Vec<Vec<u32>>) {
eprintln!("s:{:x}", s);
for row in a {
for &v in row {
eprint!("{:05x} ", v);
}
eprintln!();
}
}
}
fn main() {
let input = Input::new();
let mut solver = Solver::new(input.clone());
let mut best_res = Result::new_empty();
let part = env::var("PART").map_or(1, |v| v.parse().unwrap());
for i in 0..part {
let result = solver.solve(solver.timer.tl() * (i + 1) / part);
if result.score > best_res.score {
best_res = result;
}
break;
}
best_res.output();
eprintln!("final_score:{:?} ", best_res.score);
}