macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, Chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, Usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } #[allow(unused)] mod rnd { static mut S:usize=88172645463325252; #[inline] pub fn next()->usize{ unsafe{ S=S^S<<7; S=S^S>>9; S } } } #[allow(unused)] #[inline] fn get_time()->f64{ static mut START:f64=-1.; let t=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64(); unsafe{ if START<0.{START=t;} t-START } } #[cfg(local)] #[allow(unused)] macro_rules! debug{ ($x:expr)=>{ eprintln!("{}: {:?}",stringify!($x),$x); }; ($x:expr,$($l:expr),*)=>{ eprint!("{}: {:?}, ",stringify!($x),$x); debug!($($l),*); } } #[cfg(not(local))] #[allow(unused)] macro_rules! debug{ ($($_:expr),*)=>{} } const N:usize=256; const M:usize=2048; struct In{ edge:[[Vec;2];N] } impl In{ fn input()->In{ input!{ q:[([usize;3],[usize;3]);M] } let mut edge=[();N].map(|_|[vec![],vec![]]); for (i,v) in q.iter().enumerate(){ for (id,f) in v.0.iter().zip(v.1.iter()){ edge[*id][*f].push(i); } } In{edge} } } struct Out{ out:[bool;N], cnt:[usize;M], edge:[[Vec;2];N] } impl Out{ #[inline] // cnt,edgeの計算はしない fn new()->Out{ let mut out=[false;N]; let mut r=!0; for i in 0..N{ if i&63==0{ r=rnd::next(); } out[i]=r&1==0; r>>=1; } Out{out,cnt:[0;M],edge:[();N].map(|_|[vec![],vec![]])} } #[inline] fn re(&mut self,input:&In,r:usize){ self.cnt.fill(0); for i in 0..N{ for j in 0..2{ self.edge[i][j].clear(); for k in input.edge[i][j].iter(){ if *ki64{ self.cnt.iter().map(|x|(*x!=0) as i64).sum() } #[inline] fn change(&mut self,add:i64,idx:usize,score:&mut i64)->bool{ let mut diff=0; let f=self.out[idx]; for i in self.edge[idx][f as usize].iter(){ self.cnt[*i]-=1; diff-=(self.cnt[*i]==0) as i64; } for i in self.edge[idx][!f as usize].iter(){ self.cnt[*i]+=1; diff+=(self.cnt[*i]==1) as i64; } if add<=diff{ *score+=diff; self.out[idx]=!f; true } else{ for i in self.edge[idx][f as usize].iter(){ self.cnt[*i]+=1; } for i in self.edge[idx][!f as usize].iter(){ self.cnt[*i]-=1; } false } } } const TL:f64=1.98; fn sa(r:usize,cur:&mut Out,lim:usize)->bool{ let mut score=cur.score(); let mut iter=0; let mut up=0; let mut th=[0;256]; loop{ if iter&2047==0{ if get_time()>=TL{break;} let p=iter as f64/lim as f64; if p>=1.{break;} const T:f64=0.3; let heat=T*(1.-p); let mut id=0; while{ let r=rnd::next(); th[id]=(heat*((r&4294967295) as f64/4294967296.).ln()) as i64; th[id+1]=(heat*((r>>32) as f64/4294967296.).ln()) as i64; id+=2; id[bool;256]{ let mut out=Out::new(); let mut ans=out.out; let mut best=0; let mut pos=950; let mut iter=0; while get_time()<=TL{ iter+=1; out.re(input,pos); if sa(pos,&mut out,1000000){ ans=out.out; best=pos; pos+=4; } else{ out.out=ans; pos=best+1; } } debug!(iter); debug!(best); if cfg!(local){ println!("{best}"); } ans } fn main(){ let input=In::input(); let ans=solve(&input); if !cfg!(local){ for &i in ans.iter().rev(){ print!("{}",i as usize); } println!(); } }