結果

問題 No.5002 stick xor
ユーザー 最新の錆最新の錆
提出日時 2018-05-30 05:36:04
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 43 ms / 1,000 ms
コード長 2,682 bytes
コンパイル時間 4,384 ms
実行使用メモリ 5,092 KB
スコア 39,163
最終ジャッジ日時 2018-05-30 05:36:12
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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(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 {
                break;
            }
        }
    }

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