結果

問題 No.5013 セクスタプル (open)
ユーザー rhoorhoo
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

#![allow(non_snake_case)]
// ILS
fn 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: kick
let 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{ // todo
cand.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{ // todo
break;
}
}
// 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0