結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2025-07-26 16:57:20 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,411 ms / 2,000 ms |
| コード長 | 18,976 bytes |
| コンパイル時間 | 15,559 ms |
| コンパイル使用メモリ | 400,204 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,208,399,622 |
| 最終ジャッジ日時 | 2025-07-26 16:59:38 |
| 合計ジャッジ時間 | 90,037 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:754:7
|
754 | #[cfg(feature = "local")]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
= note: `#[warn(unexpected_cfgs)]` on by default
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:756:11
|
756 | #[cfg(not(feature = "local"))]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:536:15
|
536 | #[cfg(feature = "local")]{
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
ソースコード
#![allow(unused_imports,non_snake_case,dead_code)]
use proconio::{marker::*,*};
fn main(){
let mut K=5;
let (mut ans,mut score)=solve(5);
if ans.len()>T{
K=4;
(ans,score)=solve(4);
}
for _ in 0..6{
let (new,new_score)=solve(K);
if score<new_score{
score=new_score;
ans=new;
}
}
eprintln!("score = {}",score);
for &a in &ans{
let c=match a{
U=>'U',
D=>'D',
L=>'L',
R=>'R',
Write=>'W',
Copy=>'C',
};
println!("{c}");
}
}
// static mut score:u64=0;
fn solve(K:usize)->(Vec<Act>,u64){
get_time();
let mut a=get_input().clone();
let mut n=0;
let mut p=P::new(0,0);
let r=P::new(0,0);
let mut ans=vec![];
let get=|a:u32,i:usize|->u32{
a>>19-i&1
};
// step1
let mut ps=vec![];
for p in iterp(){
if p!=r && get(a[p],0)==1{
ps.push(p);
}
}
let route=make_route(p,Some(r),&ps);
for &np in &route[1..route.len()-1]{
ans.extend(get_path(p,np));
p=np;
if get(n,0)==0{
ans.push(Copy);
n^=a[p];
}
ans.push(Write);
a[p]^=n;
}
ans.extend(get_path(p,r));
p=r;
if get(a[r],0)==0{
ans.push(Write);
a[p]^=n;
}
ans.push(Copy);
n^=a[p];
// step2
let mut skip=std::collections::HashSet::new();
skip.insert(r);
for i in 1..K{
let mut ps=vec![];
for p in iterp(){
if !skip.contains(&p) && get(a[p],i)==1{
ps.push(p);
}
}
let mut route=make_route(p,None,&ps);
for &p in &skip{
if (p==r && get(a[p],i)==0) || (p!=r && get(a[p],i)==1){
let arg=(2..route.len()).min_by_key(|&i|route[i-1].manh(p)+p.manh(route[i])-route[i-1].manh(route[i])).unwrap();
route.insert(arg,p);
}
}
for &np in &route[1..route.len()-1]{
ans.extend(get_path(p,np));
p=np;
if get(n,i)==0{
ans.push(Copy);
n^=a[p];
}
ans.push(Write);
a[p]^=n;
}
ans.extend(get_path(p,route[route.len()-1]));
p=route[route.len()-1];
skip.insert(p);
ans.push(Copy);
n^=a[p];
}
// step3
let mut ps=vec![];
for p in iterp(){
if !skip.contains(&p) && get(a[p],K)==1{
ps.push(p);
}
}
let mut route=make_route(p,Some(r),&ps);
route.pop().unwrap();
for &p in &skip{
if (p==r && get(a[p],K)==0) || (p!=r && get(a[p],K)==1){
let arg=(2..route.len()).min_by_key(|&i|route[i-1].manh(p)+p.manh(route[i])).unwrap();
route.insert(arg,p);
}
}
for &np in &route[1..route.len()-1]{
ans.extend(get_path(p,np));
p=np;
if get(n,K)==0{
ans.push(Copy);
n^=a[p];
}
ans.push(Write);
a[p]^=n;
}
ans.extend(get_path(p,route[route.len()-1]));
p=route[route.len()-1];
skip.insert(p);
ans.push(Copy);
n^=a[p];
ans.extend(get_path(p,r));
p=r;
ans.push(Copy);
n^=a[p];
// step4
let mut ps=vec![];
let mut seen=[[false;N];N];
seen[p]=true;
for p in iterp(){
if !skip.contains(&p) && get(a[p],K+1)==1{
ps.push(p);
}
}
let mut route=make_route(p,None,&ps);
for &p in &skip{
if (p==r && get(a[p],K+1)==0) || (p!=r && get(a[p],K+1)==1){
let arg=(2..route.len()).min_by_key(|&i|route[i-1].manh(p)+p.manh(route[i])-route[i-1].manh(route[i])).unwrap();
route.insert(arg,p);
}
}
for &np in &route[1..route.len()-1]{
ans.extend(get_path(p,np));
p=np;
if get(n,K+1)==1{
ans.push(Copy);
n^=a[p];
}
ans.push(Write);
a[p]^=n;
seen[p]=true;
}
let np=route[route.len()-1];
ans.extend(get_path(p,np));
p=np;
ans.push(Copy);
n^=a[p];
ans.push(Write);
a[p]^=n;
seen[p]=true;
let mut ps=vec![];
for p in iterp(){
if !seen[p]{
ps.push(p);
}
}
let g=iterp().min_by_key(|&p|if seen[p]{a[p]}else{a[p]^n}).unwrap();
let route=make_route(p,Some(g),&ps);
for &np in &route[1..route.len()-1]{
ans.extend(get_path(p,np));
p=np;
ans.push(Write);
a[p]^=n;
}
let np=route[route.len()-1];
ans.extend(get_path(p,np));
p=np;
ans.push(Write);
a[p]^=n;
ans.push(Copy);
n^=a[p];
ans.push(Write);
a[p]^=n;
let mut s=0;
let mut res=[[0;N];N];
for p in iterp(){
s+=a[p] as u64;
res[p]=a[p]>>(19-K);
}
// unsafe{score=s};
// eprintln!("size = {}",ans.len());
(ans,s)
}
fn get_path(mut p:P,q:P)->Vec<Act>{
let mut path=vec![];
'a: while p!=q{
for i in 0..DD.len(){
let np=p+DD[i];
if p.manh(q)>np.manh(q){
path.push(DC[i]);
p=np;
continue 'a;
}
}
panic!();
}
path
}
// s->gへのパスでpsをすべて通るようなやつ
// gがNoneのときはpsのどれかが最後
fn make_route(s:P,g:Option<P>,ps:&[P])->Vec<P>{
const INF:i64=i64::MAX/10000;
let si=ps.len();
let gi=ps.len()+1;
let mi=ps.len()+2;
let get=|i:usize|if i==gi{g.unwrap()}else if i==si{s}else{ps[i]};
let mut d=vec![vec![0;ps.len()+3];ps.len()+3];
for i in 0..mi{
for j in 0..mi{
if g.is_none() && (i==gi || j==gi){
continue;
}
d[i][j]=get(i).manh(get(j)) as i64;
}
}
d[si][mi]=0;
d[mi][si]=0;
d[gi][mi]=0;
d[mi][gi]=0;
for i in 0..ps.len(){
d[i][mi]=INF;
d[mi][i]=INF;
}
// si,0..p,gi,mi,si
let mut a=vec![si];
a.extend(0..ps.len());
a.push(gi);
a.push(mi);
a.push(si);
let route=tsp(&d,&a,get_time()+0.025);
assert!(route[1]==mi || route[route.len()-2]==mi);
let route=if route[1]==mi{
// si,mi,gi,0..p,si
route[2..].iter().copied().rev().collect::<Vec<_>>()
} else{
route[..route.len()-2].iter().copied().collect::<Vec<_>>()
};
assert!(route[0]==si && route[route.len()-1]==gi);
if g.is_none(){
route[..route.len()-1].iter().map(|&i|get(i)).collect::<Vec<_>>()
} else{
route.iter().map(|&i|get(i)).collect::<Vec<_>>()
}
}
#[derive(Clone,Copy)]
enum Act{
U,D,L,R,
Write,
Copy,
}
use Act::*;
const DC:[Act;4]=[L,U,R,D];
pub fn compute_cost(g: &Vec<Vec<i64>>, ps: &Vec<usize>) -> i64 {
let mut tmp = 0;
for i in 0..ps.len() - 1 {
tmp += g[ps[i]][ps[i + 1]];
}
tmp
}
// mv: (i, dir)
pub fn apply_move(tour: &mut Vec<usize>, idx: &mut Vec<usize>, mv: &[(usize, usize)]) {
let k = mv.len();
let mut ids: Vec<_> = (0..k).collect();
ids.sort_by_key(|&i| mv[i].0);
let mut order = vec![0; k];
for i in 0..k {
order[ids[i]] = i;
}
let mut tour2 = Vec::with_capacity(mv[ids[k - 1]].0 - mv[ids[0]].0);
let mut i = ids[0];
let mut dir = 0;
loop {
let (j, rev) = if dir == mv[i].1 {
((i + 1) % k, 0)
} else {
((i + k - 1) % k, 1)
};
if mv[j].1 == rev {
if order[j] == k - 1 {
break;
} else {
i = ids[order[j] + 1];
dir = 0;
tour2.extend_from_slice(&tour[mv[j].0 + 1..mv[i].0 + 1]);
}
} else {
i = ids[order[j] - 1];
dir = 1;
tour2.extend(tour[mv[i].0 + 1..mv[j].0 + 1].iter().rev().cloned());
}
}
assert_eq!(tour2.len(), mv[ids[k - 1]].0 - mv[ids[0]].0);
tour[mv[ids[0]].0 + 1..mv[ids[k - 1]].0 + 1].copy_from_slice(&tour2);
for i in mv[ids[0]].0 + 1..mv[ids[k - 1]].0 + 1 {
idx[tour[i]] = i;
}
}
pub const FEASIBLE3: [bool; 64] = [false, false, false, true, false, true, true, true, true, true, true, false, true, false, false, false,
false, false, false, false, false, false, false, false, false, false, false, true, false, true, true, true,
true, true, true, false, true, false, false, false, false, false, false, false, false, false, false, false,
false, false, false, true, false, true, true, true, true, true, true, false, true, false, false, false];
pub fn tsp(g: &Vec<Vec<i64>>, qs: &Vec<usize>, until: f64) -> Vec<usize> {
let n = g.len();
let mut f = vec![vec![]; n];
for i in 0..n {
for j in 0..n {
if i != j {
f[i].push((g[i][j], j));
}
}
f[i].sort_by(|&(a, _), &(b, _)| a.partial_cmp(&b).unwrap());
}
let mut ps = qs.clone();
let mut idx = vec![!0; n];
let (mut min, mut min_ps) = (compute_cost(&g, &qs), ps.clone());
while get_time() < until {
let mut cost = compute_cost(&g, &ps);
for p in 0..n {
idx[ps[p]] = p;
}
loop {
let mut ok = false;
for i in 0..n {
for di in 0..2 {
'loop_ij: for &(ij, vj) in &f[ps[i + di]] {
if g[ps[i]][ps[i + 1]] - ij <= 0 {
break;
}
for dj in 0..2 {
let j = if idx[vj] == 0 && dj == 0 {
n - 1
} else {
idx[vj] - 1 + dj
};
let gain = g[ps[i]][ps[i + 1]] - ij + g[ps[j]][ps[j + 1]];
// 2-opt
if di != dj && gain - g[ps[j + dj]][ps[i + 1 - di]] > 0 {
cost -= gain - g[ps[j + dj]][ps[i + 1 - di]];
apply_move(&mut ps, &mut idx, &[(i, di), (j, dj)]);
ok = true;
break 'loop_ij;
}
// 3-opt
for &(jk, vk) in &f[ps[j + dj]] {
if gain - jk <= 0 {
break;
}
for dk in 0..2 {
let k = if idx[vk] == 0 && dk == 0 {
n - 1
} else {
idx[vk] - 1 + dk
};
if i == k || j == k {
continue;
}
let gain = gain - jk + g[ps[k]][ps[k + 1]];
if gain - g[ps[k + dk]][ps[i + 1 - di]] > 0 {
let mask = if i < j { 1 << 5 } else { 0 }
| if i < k { 1 << 4 } else { 0 }
| if j < k { 1 << 3 } else { 0 }
| di << 2 | dj << 1 | dk;
if FEASIBLE3[mask] {
cost -= gain - g[ps[k + dk]][ps[i + 1 - di]];
apply_move(&mut ps, &mut idx, &[(i, di), (j, dj), (k, dk)]);
ok = true;
break 'loop_ij;
}
}
}
}
}
}
}
}
if !ok {
break;
}
}
if min>cost{
min=cost;
min_ps = ps;
}
ps = min_ps.clone();
if n <= 4 {
break;
}
loop {
if rnd::get(2) == 0 {
// double bridge
let mut is: Vec<_> = (0..4).map(|_| rnd::get(n)).collect();
is.sort();
if is[0] == is[1] || is[1] == is[2] || is[2] == is[3] {
continue;
}
ps = ps[0..is[0]+1].iter()
.chain(ps[is[2]+1..is[3]+1].iter())
.chain(ps[is[1]+1..is[2]+1].iter())
.chain(ps[is[0]+1..is[1]+1].iter())
.chain(ps[is[3]+1..].iter())
.cloned().collect();
} else {
for _ in 0..6 {
loop {
let i=rnd::range(1,n);
let j=rnd::range(1,n);
if i < j && j - i < n - 2 {
ps = ps[0..i].iter().chain(ps[i..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
break;
}
}
}
}
break;
}
}
min_ps
}
const N:usize=10;
const T:usize=1000;
static_data!{
get_input:[[u32;N];N]|{
input!{
_n:usize,
_t:usize,
_a:[[u32;_n];_n],
}
let mut a=[[!0;N];N];
for i in 0..N{
a[i].copy_from_slice(&_a[i]);
}
a
}
}
#[macro_export]
macro_rules! static_data{
($a:ident:$t:ty|$e:expr)=>{
fn $a()->&'static $t{
use std::sync::OnceLock;
#[allow(non_upper_case_globals)]
static $a:OnceLock<$t>=OnceLock::new();
$a.get_or_init(||$e)
}
}
}
fn get_time()->f64{
static mut START:f64=0.;
let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
unsafe{
if START==0.{
START=time;
}
#[cfg(feature = "local")]{
return (time-START)*1.;
}
time-START
}
}
#[allow(unused)]
mod rnd {
static mut X2:u32=12345;
static mut X3:u32=0xcafef00d;
static mut C_X1:u64=0xd15ea5e5<<32|23456;
pub fn next()->u32{
unsafe{
let x=X3 as u64*3487286589;
let ret=(X3^X2)+(C_X1 as u32^(x>>32) as u32);
X3=X2;
X2=C_X1 as u32;
C_X1=x+(C_X1>>32);
ret
}
}
pub fn next64()->u64{
(next() as u64)<<32|next() as u64
}
pub fn nextf()->f64{
unsafe{
std::mem::transmute::<u64,f64>(0x3ff0000000000000|(next() as u64)<<20)-1.
}
}
pub fn get(n:usize)->usize{
assert!(0<n && n<=u32::MAX as usize);
next() as usize*n>>32
}
pub fn range(a:usize,b:usize)->usize{
assert!(a<b);
get(b-a)+a
}
pub fn range_skip(a:usize,b:usize,skip:usize)->usize{
assert!(a<=skip && skip<b);
let n=range(a,b-1);
n+(skip<=n) as usize
}
pub fn rangei(a:i64,b:i64)->i64{
assert!(a<b);
get((b-a) as usize) as i64+a
}
pub fn shuffle<T>(a:&mut [T]){
for i in (0..a.len()).rev(){
a.swap(i,get(i+1));
}
}
pub fn shuffle_iter<T:Copy>(a:&mut [T])->impl Iterator<Item=T>+'_{
(0..a.len()).rev().map(|i|{
a.swap(i,get(i+1));
a[i]
})
}
}
// trait RandomChoice{
// type Output;
// fn choice(&self)->Self::Output;
// }
// impl<T:Copy> RandomChoice for [T]{
// type Output=T;
// fn choice(&self)->T{
// self[rnd::get(self.len())]
// }
// }
// const DC:[char;4]=['L','U','R','D'];
const DD:[P;4]=[P{i:0,j:!0},P{i:!0,j:0},P{i:0,j:1},P{i:1,j:0}];
const DX:[P;8]=[P{i:0,j:!0},P{i:!0,j:!0},P{i:!0,j:0},P{i:!0,j:1},P{i:0,j:1},P{i:1,j:1},P{i:1,j:0},P{i:1,j:!0}];
const NULL:P=P{i:!0,j:!0};
#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash)]
struct P{
i:usize,
j:usize,
}
impl P{
fn new(i:usize,j:usize)->P{
P{i,j}
}
fn in_range(self,h:usize,w:usize)->bool{
self.i<h && self.j<w
}
fn det(self,p:P)->i64{
(self.i*p.j-self.j*p.i) as i64
}
fn dot(self,p:P)->i64{
(self.i*p.i+self.j*p.j) as i64
}
fn abs2(self)->i64{
self.dot(self)
}
fn manh(self,p:P)->usize{
let abs_diff=|a,b|(a as i64-b as i64).abs() as usize;
abs_diff(self.i,p.i)+abs_diff(self.j,p.j)
}
}
impl std::fmt::Debug for P{
fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{
write!(f,"({}, {})",self.i,self.j)
}
}
impl std::ops::Add for P{
type Output=P;
fn add(self,a:P)->P{
P{
i:self.i+a.i,
j:self.j+a.j,
}
}
}
impl std::ops::Sub for P{
type Output=P;
fn sub(self,a:P)->P{
P{
i:self.i-a.i,
j:self.j-a.j,
}
}
}
impl std::ops::Mul<usize> for P{
type Output=P;
fn mul(self,a:usize)->P{
P{
i:self.i*a,
j:self.j*a,
}
}
}
impl std::ops::Div<usize> for P{
type Output=P;
fn div(self,a:usize)->P{
P{
i:self.i/a,
j:self.j/a,
}
}
}
impl std::ops::Neg for P{
type Output=P;
fn neg(self)->P{
P{
i:self.i.wrapping_neg(),
j:self.j.wrapping_neg(),
}
}
}
macro_rules! impl_p_ops{
($t:ty,$assign_trait:ident,$assign_func:ident,$op:tt)=>{
impl std::ops::$assign_trait<$t> for P{
fn $assign_func(&mut self,a:$t){
*self=*self $ op a;
}
}
}
}
impl_p_ops!(P,AddAssign,add_assign,+);
impl_p_ops!(P,SubAssign,sub_assign,-);
impl_p_ops!(usize,MulAssign,mul_assign,*);
impl_p_ops!(usize,DivAssign,div_assign,/);
macro_rules! impl_p_index{
($t:ty)=>{
impl<T:std::ops::Index<usize>> std::ops::Index<P> for $t{
type Output=T::Output;
fn index(&self,idx:P)->&T::Output{
&self[idx.i][idx.j]
}
}
impl<T:std::ops::IndexMut<usize>> std::ops::IndexMut<P> for $t{
fn index_mut(&mut self,idx:P)->&mut T::Output{
&mut self[idx.i][idx.j]
}
}
}
}
impl_p_index!([T]);
impl_p_index!(Vec<T>);
fn iterp()->impl Iterator<Item=P>{
(0..N*N).map(|i|P::new(i/N,i%N))
}
#[cfg(feature = "local")]
include!("/home/akatsuti/cp/lib/debug_mod.rs");
#[cfg(not(feature = "local"))]
#[macro_export]macro_rules! debug{($($t:tt)*)=>{}}