結果
問題 | No.5013 セクスタプル (open) |
ユーザー |
|
提出日時 | 2024-01-07 19:22:37 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,960 ms / 2,000 ms |
コード長 | 21,624 bytes |
コンパイル時間 | 7,090 ms |
コンパイル使用メモリ | 200,680 KB |
実行使用メモリ | 9,012 KB |
スコア | 18,572 |
最終ジャッジ日時 | 2024-01-07 19:26:07 |
合計ジャッジ時間 | 210,314 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
コンパイルメッセージ
warning: unused variable: `input` --> Main.rs:135:12 | 135 | fn new(input:&Input)->State{ | ^^^^^ help: if this is intentional, prefix it with an underscore: `_input` | = note: `#[warn(unused_variables)]` on by default warning: variable `it` is assigned to, but never used --> Main.rs:247:13 | 247 | let mut it=0; | ^^ | = note: consider using `_it` instead warning: methods `get_supply` and `get_demand` are never used --> Main.rs:674:16 | 641 | impl NetworkSimplex{ | ------------------- methods in this implementation ... 674 | pub fn get_supply(&self,n:usize)->Flow{ | ^^^^^^^^^^ ... 678 | pub fn get_demand(&self,n:usize)->Flow{ | ^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: 3 warnings emitted
ソースコード
#![allow(non_snake_case)]// ILSfn main(){get_time();let input=Input::new();let mut state=State::new(&input);let mut it=0;while get_time()<=TL{it+=1;state.a=state.best;// todo: kicklet mut n=0;let mut ty=0;while n<4 && ty<10{let (i,j)=(rnd::get(2),rnd::get(N));let old=state.a[i][j];state.a[i][j]&=rnd::next() as usize;n+=(old^state.a[i][j]).count_ones();ty+=1;}optimize(&input,&mut state);}eprintln!("it = {}",it);eprintln!("skip = {}",unsafe{SKIP});eprintln!("fail = {:.2}",state.cache.iter().filter(|t|*t.1==-INF).count());eprintln!("score = {}",state.best_score);state.a=state.best;let ans=state.restore(&input);assert!(state.best_score==get_score(&input,&ans));for &(i,j) in &ans{println!("{} {}",i+1,j+1);}eprintln!("time = {}",get_time());}fn is_valid(input:&Input,is:&[usize],js:&[usize])->bool{let mut sum=[0;1<<N];for i in 0..N{for j in 0..N{sum[is[i]|js[j]]+=1;}}fast_zeta_superset(&mut sum);(0..1<<N).all(|i|sum[i]<=input.sum[i])}static mut SKIP:usize=0;// 何を揃えるのか決めてmcfで最適解を出すfn solve_flow(input:&Input,is:&[usize],js:&[usize],restore:bool)->Result<i64,Vec<(usize,usize)>>{if !is_valid(input,is,js){assert!(!restore);unsafe{SKIP+=1;};return Ok(-INF);}let mut graph=NetworkSimplex::new(2*N*N);for n in 0..N*N{graph.add_supply(n,1);graph.add_demand(n+N*N,1);let bit=input.dice[n].0;for i in 0..N{for j in 0..N{let ok=is[i]|js[j];if bit&ok==ok{let mut add=0;for k in bit_iter(is[i]).chain(bit_iter(js[j])){add+=input.dice[n].1[k] as i64;}graph.add_edge(n,N*N+i*N+j,1,-add);}}}}graph.solve();if !graph.is_valid(){assert!(!restore);return Ok(-INF);}if restore{let mut id=0;let mut pos=vec![];for n in 0..N*N{let bit=input.dice[n].0;for i in 0..N{for j in 0..N{let ok=is[i]|js[j];if bit&ok==ok{if graph.get_flow(id)>0{pos.push((i,j));}id+=1;}}}}assert!(pos.len()==N*N);Err(pos)} else{Ok(-graph.get_total()-3*is.iter().chain(js).map(|i|i.count_ones() as i64).sum::<i64>())}}#[derive(Clone)]struct State{a:[[usize;N];2],cache:HashMap<u64,i64>,best:[[usize;N];2],best_score:i64,}impl State{fn new(input:&Input)->State{State{a:[[0;N];2],cache:Default::default(),best:[[0;N];2],best_score:0,}}fn hash(&self,input:&Input)->u64{let mut h0=1;let mut h1=1;for i in 0..N{h0*=input.hash[self.a[0][i]];h1*=input.hash[self.a[1][i]];}h0+h1}fn score(&mut self,input:&Input)->i64{let hash=self.hash(input);if let Some(&n)=self.cache.get(&hash){return n;}let ret=solve_flow(input,&self.a[0],&self.a[1],false).unwrap();self.cache.insert(hash,ret);if self.best_score<ret{self.best_score=ret;self.best=self.a;}ret}fn restore(&self,input:&Input)->Vec<(usize,usize)>{solve_flow(input,&self.a[0],&self.a[1],true).unwrap_err()}}fn trans_change(input:&Input,state:&mut State,add:f64,score:&mut i64,i:usize,j:usize,new:usize)->bool{let old=state.a[i][j];let new=old^1<<new;if input.hash[new]==0{return false;}state.a[i][j]=new;let new_score=state.score(input);if add<=(new_score-*score) as f64{*score=new_score;true} else{state.a[i][j]=old;false}}fn trans_swap(input:&Input,state:&mut State,add:f64,score:&mut i64,j0:usize,j1:usize)->bool{let old0=state.a[j0/N][j0%N];let old1=state.a[j1/N][j1%N];let mut xor;let mut ty=0;loop{xor=(old0^old1)&rnd::next() as usize;if xor==0 || xor==old0^old1 && j0/N==j1/N || input.hash[state.a[j0/N][j0%N]^xor]==0 || input.hash[state.a[j1/N][j1%N]^xor]==0{ty+=1;if ty>=10{return false;}continue;}break;}state.a[j0/N][j0%N]^=xor;state.a[j1/N][j1%N]^=xor;let new_score=state.score(input);if add<=(new_score-*score) as f64{*score=new_score;true} else{state.a[j0/N][j0%N]^=xor;state.a[j1/N][j1%N]^=xor;false}}fn optimize(input:&Input,state:&mut State)->i64{let mut cand=vec![];for i in 0..2{for j in 0..N{for k in 0..N{cand.push((i,j,k));}}}for i in 0..2*N{for j in 0..2*N{for _ in 0..2{ // todocand.push((i,j,!0));}}}let mut score=state.score(input);let mut stay=0;let mut it=0;while get_time()<=TL{it+=1;rnd::shuffle(&mut cand);let old=score;for &(i,j,k) in &cand{if k!=!0{trans_change(input,state,0.,&mut score,i,j,k);} else{trans_swap(input,state,0.,&mut score,i,j);}}stay+=(old==score) as usize;if stay>=3{ // todobreak;}}// eprintln!("# try {it}");score}use std::collections::*;const INF:i64=i64::MAX/4;const N:usize=6;const TL:f64=1.95;struct Input{dice:[(usize,[usize;N]);N*N],hash:[u64;1<<N],sum:[usize;1<<N],}impl Input{fn new()->Input{let mut scan=Scanner::new();input!{scan,n:[[Usize1;N];N*N],}let mut cnt=[0;1<<N];let mut dice=[(0,[0;N]);N*N];for i in 0..N*N{let mut bit=0;for j in 0..N{bit|=1<<n[i][j];dice[i].1[n[i][j]]+=1;}dice[i].0=bit;for bit in bit_subset_iter(bit).chain(std::iter::once(bit)){cnt[bit]+=1;}}let mut hash=[0;1<<N];let mut cand=vec![];for i in 0..1<<N{if cnt[i]>=6{hash[i]=rnd::hash();cand.push(i);}}fast_zeta_superset(&mut cnt);Input{dice,hash,sum:cnt}}}fn get_score(input:&Input,a:&[(usize,usize)])->i64{let mut ids=[[!0;N];N];for (t,&(i,j)) in a.iter().enumerate(){ids[i][j]=t;}let mut score=0;for i in 0..N{for t in 0..N{if (0..N).all(|j|input.dice[ids[i][j]].1[t]>0){let sum=(0..N).map(|j|input.dice[ids[i][j]].1[t]).sum::<usize>();score+=sum-3;}if (0..N).all(|j|input.dice[ids[j][i]].1[t]>0){let sum=(0..N).map(|j|input.dice[ids[j][i]].1[t]).sum::<usize>();score+=sum-3;}}}score as i64}#[allow(unused)]fn get_time()->f64{static mut START:f64=-1.;let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();unsafe{if START<0.{START=time;}#[cfg(local)]{(time-START)*1.4}#[cfg(not(local))]{time-START}}}#[macro_export]macro_rules! timer{()=>{#[cfg(local)]let _timer=Timer(get_time());}}static mut TIME:f64=0.;struct Timer(f64);impl Drop for Timer{fn drop(&mut self){unsafe{TIME+=get_time()-self.0}}}#[allow(unused)]fn timer_ratio()->f64{unsafe{TIME/get_time()}}#[allow(unused)]mod rnd {const C:u64=0xcafef00dd15ea5e5;static mut N:u64=C;pub fn set_seed(seed:u64){unsafe{N^=seed<<1;}}pub fn next()->u32{unsafe{let mut x=N;x^=x>>22;N*=C;(x>>22+(x>>61)) as u32}}pub fn hash()->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!(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 ret=range(a,b-1);ret+(skip<=ret) 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>(list:&mut [T]){for i in (0..list.len()).rev(){list.swap(i,get(i+1));}}pub fn shuffle_iter<T:Copy>(list:&mut [T])->impl Iterator<Item=T>+'_{(0..list.len()).rev().map(|i|{list.swap(i,get(i+1));list[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())]}}// 自身と同じものは含まないfn bit_subset_iter(n:usize)->impl Iterator<Item=usize>{let mut i=n;std::iter::from_fn(move||{i=i-1&n;if i==n{None} else{Some(i)}})}struct Scanner{stack:std::str::SplitAsciiWhitespace<'static>}impl Scanner{fn new()->Self{use std::io::Read;let mut tmp=String::new();std::io::stdin().read_to_string(&mut tmp).unwrap();Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}}fn read<T:std::str::FromStr>(&mut self)->T{self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))}}#[macro_export]macro_rules! input{($scan:expr $(,)?)=>{};($scan:expr, mut $name:ident:$t:tt $($rest:tt)*)=>{let mut $name=read_value!($scan,$t);input!{$scan $($rest)*}};($scan:expr, $name:ident:$t:tt $($rest:tt)*)=>{let $name=read_value!($scan,$t);input!{$scan $($rest)*}};}#[macro_export]macro_rules! read_value{($scan:expr, ($($t:tt),*))=>{($(read_value!($scan, $t)),*)};($scan:expr, [$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()};($scan:expr, [$t:tt])=>{(0..$scan.read()).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()};($scan:expr, Chars)=>{read_value!($scan,String).chars().collect::<Vec<char>>()};($scan:expr, Usize1)=>{read_value!($scan,usize)-1};($scan:expr, $t:ty)=>{$scan.read::<$t>()};}fn bit_iter(mut n:usize)->impl Iterator<Item=usize>{std::iter::from_fn(move||if n==0{None} else{let i=n.trailing_zeros() as usize;n^=1<<i;Some(i)})}// https://github.com/brunodccarvalho/competitive/// © 2022 brunodccarvalho// https://opensource.org/license/mit/// thank you!mod network_simplex{pub type Flow=i64;pub type Cost=i64;pub type CostSum=i64;#[derive(Clone)]struct LinkedList{n:usize,next:Vec<usize>,prev:Vec<usize>,}impl LinkedList{fn new(l:usize,n:usize)->LinkedList{LinkedList{n,next:(0..n).map(|_|0).chain(n..n+l).collect(),prev:(0..n).map(|_|0).chain(n..n+l).collect(),}}fn rep(&self,l:usize)->usize{l+self.n}fn head(&self,l:usize)->usize{self.next[self.rep(l)]}fn tail(&self,l:usize)->usize{self.prev[self.rep(l)]}fn link(&mut self,u:usize,v:usize){self.next[u]=v;self.prev[v]=u;}fn push(&mut self,l:usize,n:usize){self.link(self.tail(l),n);self.link(n,self.rep(l));}fn erase(&mut self,n:usize){self.link(self.prev[n],self.next[n])}}#[derive(Clone,Default)]struct Node{parent:usize,pred:usize,supply:Flow,pot:Cost}#[derive(Clone)]pub struct Edge{node:(usize,usize),cap:Flow,cost:Cost,flow:Flow,state:i8}pub struct NetworkSimplex{v:usize,e:usize,next_arc:usize,block_size:usize,node:Vec<Node>,edge:Vec<Edge>,childs:LinkedList,bfs:Vec<usize>}impl NetworkSimplex{pub fn new(v:usize)->NetworkSimplex{NetworkSimplex{v,e:0,next_arc:0,block_size:0,node:vec![Node::default();v+1],edge:vec![],childs:LinkedList::new(0,0),bfs:vec![]}}pub fn add_supply(&mut self,u:usize,supply:Flow){self.node[u].supply+=supply;}pub fn add_demand(&mut self,u:usize,supply:Flow){self.node[u].supply-=supply;}// idは順番に振られるpub fn add_edge(&mut self,u:usize,v:usize,cap:Flow,cost:Cost)->usize{assert!(u<self.v && v<self.v);self.edge.push(Edge{node:(u,v),flow:0,cap,cost,state:0});self.e+=1;self.e-1}pub fn get_flow(&self,e:usize)->Flow{self.edge[e].flow}pub fn get_supply(&self,n:usize)->Flow{self.get_flow(self.e+n)}pub fn get_demand(&self,n:usize)->Flow{-self.get_flow(self.e+n)}pub fn get_total(&self)->CostSum{(0..self.e).map(|e|self.edge[e].cost as CostSum*self.edge[e].flow as CostSum).sum()}pub fn is_valid(&self)->bool{(self.e..self.edge.len()).all(|e|self.edge[e].flow<=0)}fn reduced_cost(&self,e:usize)->Cost{let (u,v)=self.edge[e].node;self.edge[e].cost+self.node[u].pot-self.node[v].pot}fn select_pivot_edge(&mut self)->usize{let mut min=0;let mut in_arc=!0;let mut cnt=self.block_size;for _ in 0..self.edge.len(){let next=self.edge[self.next_arc].state as Cost*self.reduced_cost(self.next_arc);if next<min{min=next;in_arc=self.next_arc;}cnt-=1;if cnt==0{if min<0{break;}cnt=self.block_size;}self.next_arc+=1;self.next_arc*=(self.next_arc!=self.edge.len()) as usize;}in_arc}fn pivot(&mut self,in_arc:usize){let (mut u_in,mut v_in)=self.edge[in_arc].node;let mut a=u_in;let mut b=v_in;while a!=b{a=[self.node[a].parent,v_in][(self.node[a].parent==!0) as usize];b=[self.node[b].parent,u_in][(self.node[b].parent==!0) as usize];}let lca=a;if self.edge[in_arc].state==!0{std::mem::swap(&mut u_in,&mut v_in);}let mut side=0u8;let mut flow_delta=self.edge[in_arc].cap;let mut u_out=!0;let mut u=u_in;while u!=lca && 0<flow_delta{let e=self.node[u].pred;let edge_down= u==self.edge[e].node.1;let to_saturate=if edge_down{self.edge[e].cap-self.edge[e].flow}else {self.edge[e].flow};if to_saturate<flow_delta{flow_delta=to_saturate;u_out=u;side=1;}u=self.node[u].parent;}u=v_in;while u!=lca{let e=self.node[u].pred;let edge_up= u==self.edge[e].node.0;let to_saturate=if edge_up{self.edge[e].cap-self.edge[e].flow}else{self.edge[e].flow};if to_saturate<=flow_delta{flow_delta=to_saturate;u_out=u;side=2;}u=self.node[u].parent;}if 0<flow_delta{let delta=self.edge[in_arc].state as Flow*flow_delta;self.edge[in_arc].flow+=delta;let mut u=self.edge[in_arc].node.0;while u!=lca{let e=self.node[u].pred;self.edge[e].flow+=((u!=self.edge[e].node.0) as Flow*2-1)*delta;u=self.node[u].parent;}u=self.edge[in_arc].node.1;while u!=lca{let e=self.node[u].pred;self.edge[e].flow+=((u==self.edge[e].node.0) as Flow*2-1)*delta;u=self.node[u].parent;}}if side==0{self.edge[in_arc].state=-self.edge[in_arc].state;return;}let out_arc=self.node[u_out].pred;self.edge[in_arc].state=0;self.edge[out_arc].state=1-(self.edge[out_arc].flow!=0) as i8*2;if side==2{std::mem::swap(&mut u_in,&mut v_in);}let mut s=0;u=u_in;while u!=u_out{self.bfs[s]=u;s+=1;u=self.node[u].parent;}assert!(s<=self.v);for i in (0..s).rev(){let u=self.bfs[i];let p=self.node[u].parent;self.childs.erase(p);self.childs.push(u,p);self.node[p].parent=u;self.node[p].pred=self.node[u].pred;}self.childs.erase(u_in);self.childs.push(v_in,u_in);self.node[u_in].parent=v_in;self.node[u_in].pred=in_arc;let delta=self.reduced_cost(in_arc)*((u_in!=self.edge[in_arc].node.0) as Cost*2-1);self.bfs[0]=u_in;let mut i=0;s=1;while i<s{let u=self.bfs[i];self.node[u].pot+=delta;let l=self.childs.rep(u);let mut v=self.childs.head(u);while v!=l{self.bfs[s]=v;s+=1;v=self.childs.next[v];}i+=1;}}pub fn solve(&mut self){let mut inf=1;for e in 0..self.e{self.edge[e].flow=0;self.edge[e].state=1;inf+=self.edge[e].cost.abs();}self.edge.reserve(self.e+self.v);self.bfs.resize(self.v+1,0);self.childs=LinkedList::new(self.v+1,self.v+1);let root=self.v;self.node[root]=Node{parent:!0,pred:!0,supply:0,pot:0};for u in 0..self.v{let e=u+self.e;self.node[u].parent=root;self.node[u].pred=e;self.childs.push(root,u);let supply=self.node[u].supply;if 0<=supply{self.node[u].pot=-inf;self.edge.push(Edge{node:(u,root),cap:supply,cost:inf,flow:supply,state:0});}else{self.node[u].pot=inf;self.edge.push(Edge{node:(root,u),cap:-supply,cost:inf,flow:-supply,state:0});}}self.block_size=((self.edge.len() as f64).sqrt().ceil() as usize).max(10.min(self.v+1));self.next_arc=0;loop{let in_arc=self.select_pivot_edge();if in_arc==!0{break;}self.pivot(in_arc);}}}}use network_simplex::*;fn fast_zeta_superset(a:&mut [usize]){let mut i=1;while i<a.len(){for j in 0..a.len(){if j&i==0{a[j]+=a[j^i];}}i*=2;}}