#261507 (Rust) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: 最新の錆
• 提出日時: 2018-05-30 05:57:29
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 35 ms / 1,000 ms
• コード長: 4,148 bytes
• コンパイル時間: 5,515 ms
• 実行使用メモリ: 5,100 KB
• スコア: 39,231
• 最終ジャッジ日時: 2018-05-30 05:57:37
• ジャッジサーバーID （参考情報）: judge7 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	33 ms; 5,096 KB
testcase_01	AC	33 ms; 5,092 KB
testcase_02	AC	34 ms; 5,096 KB
testcase_03	AC	34 ms; 5,096 KB
testcase_04	AC	32 ms; 5,096 KB
testcase_05	AC	32 ms; 5,096 KB
testcase_06	AC	33 ms; 5,092 KB
testcase_07	AC	35 ms; 5,092 KB
testcase_08	AC	34 ms; 5,096 KB
testcase_09	AC	32 ms; 5,100 KB
testcase_10	AC	34 ms; 5,096 KB
testcase_11	AC	33 ms; 5,100 KB
testcase_12	AC	33 ms; 5,100 KB
testcase_13	AC	33 ms; 5,096 KB
testcase_14	AC	33 ms; 5,092 KB
testcase_15	AC	34 ms; 5,092 KB
testcase_16	AC	33 ms; 5,092 KB
testcase_17	AC	33 ms; 5,092 KB
testcase_18	AC	33 ms; 5,096 KB
testcase_19	AC	33 ms; 5,100 KB
testcase_20	AC	33 ms; 5,100 KB
testcase_21	AC	33 ms; 5,096 KB
testcase_22	AC	34 ms; 5,096 KB
testcase_23	AC	33 ms; 5,096 KB
testcase_24	AC	33 ms; 5,096 KB
testcase_25	AC	32 ms; 5,096 KB
testcase_26	AC	33 ms; 5,092 KB
testcase_27	AC	33 ms; 5,092 KB
testcase_28	AC	33 ms; 5,096 KB
testcase_29	AC	32 ms; 5,092 KB
testcase_30	AC	33 ms; 5,092 KB
testcase_31	AC	33 ms; 5,096 KB

ソースコード

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