結果
| 問題 | No.5002 stick xor |
| ユーザー |
 最新の錆
|
| 提出日時 | 2018-05-30 06:07:34 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 1,000 ms |
| コード長 | 5,766 bytes |
| コンパイル時間 | 7,343 ms |
| 実行使用メモリ | 5,108 KB |
| スコア | 39,231 |
| 最終ジャッジ日時 | 2018-05-30 06:07:47 |
|
ジャッジサーバーID （参考情報） |
judge6 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
use std::io::{Read, stdin};use std::cmp::max;fn main() {let mut buf = String::new();stdin().read_to_string(&mut buf).unwrap();let mut tok = buf.split_whitespace();let mut get = || tok.next().unwrap();macro_rules! get {($t:ty) => (get().parse::<$t>().unwrap());() => (get!(usize));}let n = get!();let k = get!();let mut ls = vec![0; k];let mut lmax = 0;for i in 0..ls.len() {ls[i] = get!();lmax = max(lmax, ls[i]);}let mut lcount = vec![0; lmax+1];for &l in ls.iter() {lcount[l] += 1;}let mut field = vec![vec![]; n];for i in 0..field.len() {let a = get().as_bytes();for j in 0..a.len() {field[i].push((a[j] - b'0') as i32);}}let mut ans = vec![vec![]; lmax+1];for l in 1..lmax {let l = lmax - l;while lcount[l] > 0 {if let Some((x, y, h)) = search_max(n, &field, l) {lcount[l] -= 1;ans[l].push((x, y, h));if h {for x in x..x+l {field[y][x] = 1 - field[y][x];}} else {for y in y..y+l {field[y][x] = 1 - field[y][x];}}} else if lcount[l] % 2 == 0 {break;} else {let (x, y, h) = search_any(n, &field, l);lcount[l] -= 1;ans[l].push((x, y, h));if h {for x in x..x+l {field[y][x] = 1 - field[y][x];}} else {for y in y..y+l {field[y][x] = 1 - field[y][x];}}break;}}}for l in 1..lmax {let l = lmax - l;while lcount[l] > 1 {if let Some((x, y, h)) = search_side(n, &field, l+1) {lcount[l] -= 2;if h {ans[l].push((x, y, h));ans[l].push((x+1, y, h));field[y][x] = 1 - field[y][x];field[y][x+l] = 1 - field[y][x+l];} else {ans[l].push((x, y, h));ans[l].push((x, y+1, h));field[y][x] = 1 - field[y][x];field[y+l][x] = 1 - field[y+l][x];}} else {break;}}}for y in 0..n {for x in 0..n {if field[y][x] != 0 {ans[1].push((x, y, true));}}}for &l in ls.iter() {if let Some((x, y, h)) = ans[l].pop() {if h {println!("{0} {1} {0} {2}", y+1, x+1, x+l);} else {println!("{1} {0} {2} {0}", x+1, y+1, y+l);}} else {println!("1 1 1 {0}", l);}}}fn search_max(n: usize, field: &Vec<Vec<i32>>, l: usize) -> Option<(usize, usize, bool)> {let mut max_cnt = -1;let mut sel_x = 0;let mut sel_y = 0;let mut hori = false;for i in 0..n {for j in 0..n-l+1 {let mut cnt = 0;for p in j..j+l {cnt += field[i][p];}if cnt+cnt > l as i32 && cnt > max_cnt {max_cnt = cnt;sel_x = j;sel_y = i;hori = true;}let mut cnt = 0;for p in j..j+l {cnt += field[p][i];}if cnt+cnt > l as i32 && cnt > max_cnt {max_cnt = cnt;sel_x = i;sel_y = j;hori = false;}}}if max_cnt < 0 {None} else {Some((sel_x, sel_y, hori))}}fn search_any(n: usize, field: &Vec<Vec<i32>>, l: usize) -> (usize, usize, bool) {let mut max_cnt = -1;let mut sel_x = 0;let mut sel_y = 0;let mut hori = false;for i in 0..n {for j in 0..n-l+1 {let mut cnt = 0;for p in j..j+l {cnt += field[i][p];}if cnt > max_cnt {max_cnt = cnt;sel_x = j;sel_y = i;hori = true;}let mut cnt = 0;for p in j..j+l {cnt += field[p][i];}if cnt > max_cnt {max_cnt = cnt;sel_x = i;sel_y = j;hori = false;}}}(sel_x, sel_y, hori)}fn search_side(n: usize, field: &Vec<Vec<i32>>, l: usize) -> Option<(usize, usize, bool)> {let mut max_cnt = -1;let mut sel_x = 0;let mut sel_y = 0;let mut hori = false;for i in 0..n {for j in 0..n-l+1 {let mut cnt = 0;cnt += field[i][j];cnt += field[i][j+l-1];if cnt+cnt > l as i32 && cnt > max_cnt {max_cnt = cnt;sel_x = j;sel_y = i;hori = true;}let mut cnt = 0;cnt += field[j][i];cnt += field[j+l-1][i];if cnt+cnt > l as i32 && cnt > max_cnt {max_cnt = cnt;sel_x = i;sel_y = j;hori = false;}}}if max_cnt < 0 {None} else {Some((sel_x, sel_y, hori))}}