/** * _ _ __ _ _ _ _ _ _ _ * | | | | / / | | (_) | (_) | | (_) | | * | |__ __ _| |_ ___ ___ / /__ ___ _ __ ___ _ __ ___| |_ _| |_ ___ _____ ______ _ __ _ _ ___| |_ ______ ___ _ __ _ _ __ _ __ ___| |_ ___ * | '_ \ / _` | __/ _ \ / _ \ / / __/ _ \| '_ ` _ \| '_ \ / _ \ __| | __| \ \ / / _ \______| '__| | | / __| __|______/ __| '_ \| | '_ \| '_ \ / _ \ __/ __| * | | | | (_| | || (_) | (_) / / (_| (_) | | | | | | |_) | __/ |_| | |_| |\ V / __/ | | | |_| \__ \ |_ \__ \ | | | | |_) | |_) | __/ |_\__ \ * |_| |_|\__,_|\__\___/ \___/_/ \___\___/|_| |_| |_| .__/ \___|\__|_|\__|_| \_/ \___| |_| \__,_|___/\__| |___/_| |_|_| .__/| .__/ \___|\__|___/ * | | | | | | * |_| |_| |_| * * https://github.com/hatoo/competitive-rust-snippets */ #[allow(unused_imports)] use std::cmp::{max, min, Ordering}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::io::{stdin, stdout, BufWriter, Write}; #[allow(unused_imports)] use std::iter::FromIterator; mod util { use std::fmt::Debug; use std::io::{stdin, stdout, BufWriter, StdoutLock}; use std::str::FromStr; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn chars() -> Vec { line().chars().collect() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn with_bufwriter) -> ()>(f: F) { let out = stdout(); let writer = BufWriter::new(out.lock()); f(writer) } } #[allow(unused_macros)] macro_rules ! get { ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ;; ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; ( $ t : ty ;; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ;; ) ) . collect ::< Vec < _ >> ( ) } ; } #[allow(unused_macros)] macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } } const BIG_STACK_SIZE: bool = false; #[allow(dead_code)] fn main() { use std::thread; if BIG_STACK_SIZE { thread::Builder::new() .stack_size(32 * 1024 * 1024) .name("solve".into()) .spawn(solve) .unwrap() .join() .unwrap(); } else { solve(); } } #[derive(Eq, PartialEq, Clone, Debug)] /// Equivalent to std::cmp::Reverse pub struct Rev(pub T); impl PartialOrd for Rev { fn partial_cmp(&self, other: &Rev) -> Option { other.0.partial_cmp(&self.0) } } impl Ord for Rev { fn cmp(&self, other: &Rev) -> Ordering { other.0.cmp(&self.0) } } #[derive(Debug)] #[allow(dead_code)] pub struct Xorshift { seed: u64, } impl Xorshift { #[allow(dead_code)] pub fn new() -> Xorshift { Xorshift { seed: 0xf0fb588ca2196dac, } } #[allow(dead_code)] pub fn with_seed(seed: u64) -> Xorshift { Xorshift { seed: seed } } #[inline(always)] #[allow(dead_code)] pub fn next(&mut self) -> u64 { self.seed = self.seed ^ (self.seed << 13); self.seed = self.seed ^ (self.seed >> 7); self.seed = self.seed ^ (self.seed << 17); self.seed } #[inline(always)] #[allow(dead_code)] pub fn rand(&mut self, m: u64) -> u64 { self.next() % m } #[inline(always)] #[allow(dead_code)] pub fn randf(&mut self) -> f64 { use std::mem; const UPPER_MASK: u64 = 0x3FF0000000000000; const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF; let tmp = UPPER_MASK | (self.next() & LOWER_MASK); let result: f64 = unsafe { mem::transmute(tmp) }; result - 1.0 } } fn rand_action(rng: &mut Xorshift, n: usize, l: usize) -> (bool, usize, usize) { loop { let t = rng.rand(2) == 0; let y = rng.rand(n as u64) as usize; let x = rng.rand(n as u64) as usize; if (t && x + l <= n) || (!t && y + l <= n) { break (t, y, x); } } } fn score((t, y, x): (bool, usize, usize), l: usize, n: usize) -> f64 { let s = if t { min(y, n - y) } else { min(x, n - x) }; 0.01 * s as f64 / n as f64 } struct Field { f1: [u64; 60], f2: [u64; 60], } impl Field { fn new(init: &Vec>) -> Field { let n = init.len(); let mut f1 = [0; 60]; let mut f2 = [0; 60]; for y in 0..n { for x in 0..n { if init[y][x] { f1[y] |= 1 << x; f2[x] |= 1 << y; } } } Field { f1, f2 } } #[inline] fn apply(&mut self, (t, y, x): (bool, usize, usize), l: usize) { let w = (1 << l) - 1; if t { self.f1[y] ^= w << x; for x in x..x + l { self.f2[x] ^= 1 << y; } } else { self.f2[x] ^= w << y; for y in y..y + l { self.f1[y] ^= 1 << x; } } } #[inline] fn count_b(&self, (t, y, x): (bool, usize, usize), l: usize) -> f64 { let w = (1 << l) - 1; if t { (self.f1[y] & (w << x)).count_ones() as f64 } else { (self.f2[x] & (w << y)).count_ones() as f64 } } } use std::time::{Duration, Instant}; fn solve() { let start = Instant::now(); let (n, k) = get!(usize, usize); let ls = get!(usize;;); let field: Vec> = (0..n) .map(|_| util::line().chars().map(|c| c == '1').collect()) .collect(); let mut rng = Xorshift::new(); let mut field = Field::new(&field); let mut ans = vec![(true, 0, 0); k]; let idx: Vec = (0..k).collect(); //idx.sort_by_key(|&i| Rev(ls[i])); for i in idx { let l = ls[i]; let mut val = -1000.0; let mut tyx = (false, 0, 0); for y in 0..n { for x in 0..n - l { let b = field.count_b((true, y, x), l) + score((true, y, x), l, n); if (b == val && rng.randf() > 0.4) || b > val { tyx = (true, y, x); val = b; } } } for y in 0..n - l { for x in 0..n { let b = field.count_b((false, y, x), l) + score((false, y, x), l, n); if (b == val && rng.randf() > 0.4) || b > val { tyx = (false, y, x); val = b; } } } field.apply(tyx, l); ans[i] = tyx; /* let tyx = rand_action(&mut rng, n, l); field.apply(tyx, l); ans.push(tyx); */ } let mut total = 0.0; let mut best = 0.0; let mut best_ans = ans.clone(); let mut t = 1.0; let lim = Duration::from_millis(980); for c in 0.. { if c % 1000 == 0 && Instant::now() - start >= lim { debug!(c); break; } let i = rng.rand(k as u64) as usize; let l = ls[i]; field.apply(ans[i], l); let before = field.count_b(ans[i], l); let action = rand_action(&mut rng, n, l); let after = field.count_b(action, l); let d = after - before; if d > 0.0 || rng.randf() <= (d / (t * 0.01)).exp() { ans[i] = action; field.apply(action, l); total += d; } else { field.apply(ans[i], l); } if total > best { best = total; best_ans = ans.clone(); } t *= 0.999999; } debug!(t); util::with_bufwriter(|mut out| { for (i, (t, y, x)) in best_ans.into_iter().enumerate() { if t { writeln!(out, "{} {} {} {}", y + 1, x + 1, y + 1, x + ls[i]).unwrap(); } else { writeln!(out, "{} {} {} {}", y + 1, x + 1, y + ls[i], x + 1).unwrap(); } } }); }