結果

問題 No.5013 セクスタプル (open)
ユーザー rhoorhoo
提出日時 2024-01-07 20:58:25
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,903 ms / 2,000 ms
コード長 22,489 bytes
コンパイル時間 3,211 ms
コンパイル使用メモリ 214,964 KB
実行使用メモリ 6,676 KB
スコア 18,569
最終ジャッジ日時 2024-01-07 21:01:45
合計ジャッジ時間 198,740 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,901 ms
6,676 KB
testcase_01 AC 1,902 ms
6,676 KB
testcase_02 AC 1,902 ms
6,676 KB
testcase_03 AC 1,902 ms
6,676 KB
testcase_04 AC 1,902 ms
6,676 KB
testcase_05 AC 1,902 ms
6,676 KB
testcase_06 AC 1,902 ms
6,676 KB
testcase_07 AC 1,901 ms
6,676 KB
testcase_08 AC 1,901 ms
6,676 KB
testcase_09 AC 1,902 ms
6,676 KB
testcase_10 AC 1,903 ms
6,676 KB
testcase_11 AC 1,902 ms
6,676 KB
testcase_12 AC 1,902 ms
6,676 KB
testcase_13 AC 1,902 ms
6,676 KB
testcase_14 AC 1,902 ms
6,676 KB
testcase_15 AC 1,901 ms
6,676 KB
testcase_16 AC 1,903 ms
6,676 KB
testcase_17 AC 1,902 ms
6,676 KB
testcase_18 AC 1,903 ms
6,676 KB
testcase_19 AC 1,902 ms
6,676 KB
testcase_20 AC 1,902 ms
6,676 KB
testcase_21 AC 1,902 ms
6,676 KB
testcase_22 AC 1,901 ms
6,676 KB
testcase_23 AC 1,901 ms
6,676 KB
testcase_24 AC 1,902 ms
6,676 KB
testcase_25 AC 1,902 ms
6,676 KB
testcase_26 AC 1,902 ms
6,676 KB
testcase_27 AC 1,902 ms
6,676 KB
testcase_28 AC 1,902 ms
6,676 KB
testcase_29 AC 1,902 ms
6,676 KB
testcase_30 AC 1,901 ms
6,676 KB
testcase_31 AC 1,902 ms
6,676 KB
testcase_32 AC 1,902 ms
6,676 KB
testcase_33 AC 1,902 ms
6,676 KB
testcase_34 AC 1,902 ms
6,676 KB
testcase_35 AC 1,902 ms
6,676 KB
testcase_36 AC 1,902 ms
6,676 KB
testcase_37 AC 1,901 ms
6,676 KB
testcase_38 AC 1,902 ms
6,676 KB
testcase_39 AC 1,902 ms
6,676 KB
testcase_40 AC 1,902 ms
6,676 KB
testcase_41 AC 1,902 ms
6,676 KB
testcase_42 AC 1,902 ms
6,676 KB
testcase_43 AC 1,902 ms
6,676 KB
testcase_44 AC 1,902 ms
6,676 KB
testcase_45 AC 1,902 ms
6,676 KB
testcase_46 AC 1,902 ms
6,676 KB
testcase_47 AC 1,903 ms
6,676 KB
testcase_48 AC 1,902 ms
6,676 KB
testcase_49 AC 1,903 ms
6,676 KB
testcase_50 AC 1,902 ms
6,676 KB
testcase_51 AC 1,902 ms
6,676 KB
testcase_52 AC 1,901 ms
6,676 KB
testcase_53 AC 1,902 ms
6,676 KB
testcase_54 AC 1,901 ms
6,676 KB
testcase_55 AC 1,902 ms
6,676 KB
testcase_56 AC 1,903 ms
6,676 KB
testcase_57 AC 1,902 ms
6,676 KB
testcase_58 AC 1,903 ms
6,676 KB
testcase_59 AC 1,901 ms
6,676 KB
testcase_60 AC 1,902 ms
6,676 KB
testcase_61 AC 1,902 ms
6,676 KB
testcase_62 AC 1,901 ms
6,676 KB
testcase_63 AC 1,902 ms
6,676 KB
testcase_64 AC 1,902 ms
6,676 KB
testcase_65 AC 1,903 ms
6,676 KB
testcase_66 AC 1,902 ms
6,676 KB
testcase_67 AC 1,901 ms
6,676 KB
testcase_68 AC 1,902 ms
6,676 KB
testcase_69 AC 1,902 ms
6,676 KB
testcase_70 AC 1,902 ms
6,676 KB
testcase_71 AC 1,902 ms
6,676 KB
testcase_72 AC 1,902 ms
6,676 KB
testcase_73 AC 1,903 ms
6,676 KB
testcase_74 AC 1,902 ms
6,676 KB
testcase_75 AC 1,902 ms
6,676 KB
testcase_76 AC 1,902 ms
6,676 KB
testcase_77 AC 1,902 ms
6,676 KB
testcase_78 AC 1,902 ms
6,676 KB
testcase_79 AC 1,902 ms
6,676 KB
testcase_80 AC 1,902 ms
6,676 KB
testcase_81 AC 1,902 ms
6,676 KB
testcase_82 AC 1,902 ms
6,676 KB
testcase_83 AC 1,902 ms
6,676 KB
testcase_84 AC 1,902 ms
6,676 KB
testcase_85 AC 1,902 ms
6,676 KB
testcase_86 AC 1,902 ms
6,676 KB
testcase_87 AC 1,902 ms
6,676 KB
testcase_88 AC 1,902 ms
6,676 KB
testcase_89 AC 1,901 ms
6,676 KB
testcase_90 AC 1,902 ms
6,676 KB
testcase_91 AC 1,902 ms
6,676 KB
testcase_92 AC 1,902 ms
6,676 KB
testcase_93 AC 1,901 ms
6,676 KB
testcase_94 AC 1,902 ms
6,676 KB
testcase_95 AC 1,902 ms
6,676 KB
testcase_96 AC 1,902 ms
6,676 KB
testcase_97 AC 1,902 ms
6,676 KB
testcase_98 AC 1,902 ms
6,676 KB
testcase_99 AC 1,902 ms
6,676 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `input`
   --> Main.rs:112:12
    |
112 |     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 `valid` is assigned to, but never used
   --> Main.rs:257:17
    |
257 |         let mut valid=0;
    |                 ^^^^^
    |
    = note: consider using `_valid` instead

warning: methods `get_supply` and `get_demand` are never used
   --> Main.rs:690:16
    |
657 |     impl NetworkSimplex{
    |     ------------------- methods in this implementation
...
690 |         pub fn get_supply(&self,n:usize)->Flow{
    |                ^^^^^^^^^^
...
694 |         pub fn get_demand(&self,n:usize)->Flow{
    |                ^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 3 warnings emitted

ソースコード

diff # 

#![allow(non_snake_case)]


// SA


fn main(){
    get_time();
    let input=Input::new();

    let mut sa=SA::new(State::new(&input));
    for tl in multi_start_iter(2,TL){
        sa.solve(&input,tl);
    }
    // sa.solve(&input,TL);
    let ans=sa.state.restore(&input);
    eprintln!("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 trans(input:&Input,state:&mut State,add:f64,score:&mut i64)->bool{
    if rnd::nextf()<=0.5{ // todo
        trans_change(input,state,add,score,rnd::get(2),rnd::get(N),rnd::get(N))
    } else{
        trans_swap(input,state,add,score,rnd::get(2*N),rnd::get(2*N))
    }
}


struct SA{
    start:f64,
    tl:f64,
    time:f64,
    heat:f64,
    table:[f64;65536],
    state:State,
}
impl SA{
    fn new(state:State)->SA{
        let mut table=[0.;65536];
        for i in 0..65536{
            table[i]=((i as f64+0.5)/65536.).ln();
        }
        rnd::shuffle(&mut table);

        SA{
            start:0.,
            tl:0.,
            time:0.,
            heat:0.,
            table,
            state,
        }
    }
    
    fn update(&mut self)->bool{
        self.time=(get_time()-self.start)/self.tl;
        if self.time>=1.{
            return false;
        }

        // todo
        const T0:f64=1.5;
        self.heat=T0*(1.-self.time);

        true
    }
    
    fn solve(&mut self,input:&Input,tl:f64){
        self.start=get_time();
        assert!(self.start<tl);
        self.tl=tl-self.start;
        
        let mut valid=0;
        let mut score=self.state.score(input);
        let mut best_score=score;
        let mut best=self.state.clone();
        let mut iter=0;

        while iter&255!=0 || self.update(){
            iter+=1;
            let add=self.heat*self.table[iter&65535]; // 最大化
            // let add=0.;
            
            valid+=trans(input,&mut self.state,add,&mut score) as usize;

            if 0.1<self.time{
                if best_score<score{
                    best_score=score;
                    best=self.state.clone();
                    continue;
                }
            }
        }

        assert!(self.state.score(input)==score);
        self.state=best;

        // eprintln!("score = {}",best_score);
        // eprintln!("last = {}",score);
        // eprintln!("iter = {}",iter);
        // eprintln!("ratio = {:.3}",valid as f64/iter as f64);
    }
}




use std::collections::*;

const INF:i64=i64::MAX/4;
const N:usize=6;
const TL:f64=1.9;



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;
    }
}


fn multi_start_iter(mut n:usize,tl:f64)->impl Iterator<Item=f64>{
    std::iter::from_fn(move||{
        if n==0{
            None
        } else{
            let time=get_time();
            let ret=Some((tl-time)/n as f64+time);
            n-=1;
            ret
        }
    })
}
0