/** * _ _ __ _ _ _ _ _ _ _ * | | | | / / | | (_) | (_) | | (_) | | * | |__ __ _| |_ ___ ___ / /__ ___ _ __ ___ _ __ ___| |_ _| |_ ___ _____ ______ _ __ _ _ ___| |_ ______ ___ _ __ _ _ __ _ __ ___| |_ ___ * | '_ \ / _` | __/ _ \ / _ \ / / __/ _ \| '_ ` _ \| '_ \ / _ \ __| | __| \ \ / / _ \______| '__| | | / __| __|______/ __| '_ \| | '_ \| '_ \ / _ \ __/ __| * | | | | (_| | || (_) | (_) / / (_| (_) | | | | | | |_) | __/ |_| | |_| |\ 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(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 apply((t, y, x): (bool, usize, usize), l: usize, field: &mut Vec>) { if t { for x in x..x + l { field[y][x] = !field[y][x]; } } else { for y in y..y + l { field[y][x] = !field[y][x]; } } } fn count_b((t, y, x): (bool, usize, usize), l: usize, field: &Vec>) -> f64 { let mut b = 0.0; if t { for x in x..x + l { if field[y][x] { b += 1.0; } } } else { for y in y..y + l { if field[y][x] { b += 1.0; } } } b } 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 } use std::time::{Duration, Instant}; fn solve() { let start = Instant::now(); let (n, k) = get!(usize, usize); let ls = get!(usize;;); let mut field: Vec> = (0..n) .map(|_| util::line().chars().map(|c| c == '1').collect()) .collect(); // Find baseline with simple greedy let mut ans = Vec::new(); for &l in &ls { let mut val = -1000.0; let mut tyx = (false, 0, 0); for y in 0..n { for x in 0..n - l { let b = count_b((true, y, x), l, &field); if b > val { tyx = (true, y, x); val = b; } } } for y in 0..n - l { for x in 0..n { let b = count_b((false, y, x), l, &field); if b > val { tyx = (false, y, x); val = b; } } } apply(tyx, l, &mut field); ans.push(tyx); } let mut rng = Xorshift::new(); for c in 0.. { if c % 100 == 0 && Instant::now() - start >= Duration::from_millis(980) { break; } let i = rng.rand(k as u64) as usize; let l = ls[i]; apply(ans[i], l, &mut field); let mut val = -1000.0; for y in 0..n { for x in 0..n { if x + l < n { let b = count_b((true, y, x), l, &field) + score((true, y, x), l, n); if b > val { ans[i] = (true, y, x); val = b; } } if y + l < n { let b = count_b((false, y, x), l, &field) + score((false, y, x), l, n); if b > val { ans[i] = (false, y, x); val = b; } } } } apply(ans[i], l, &mut field); } util::with_bufwriter(|mut out| { for (i, (t, y, x)) in 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(); } } }); }