結果

問題 No.5002 stick xor
ユーザー 最新の錆最新の錆
提出日時 2018-05-30 06:24:06
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 37 ms / 1,000 ms
コード長 6,506 bytes
コンパイル時間 4,029 ms
実行使用メモリ 5,100 KB
スコア 39,765
最終ジャッジ日時 2018-05-30 06:24:12
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
5,100 KB
testcase_01 AC 35 ms
5,092 KB
testcase_02 AC 35 ms
5,096 KB
testcase_03 AC 37 ms
5,100 KB
testcase_04 AC 37 ms
5,092 KB
testcase_05 AC 36 ms
5,096 KB
testcase_06 AC 37 ms
5,092 KB
testcase_07 AC 34 ms
5,100 KB
testcase_08 AC 35 ms
5,100 KB
testcase_09 AC 37 ms
5,096 KB
testcase_10 AC 37 ms
5,092 KB
testcase_11 AC 36 ms
5,096 KB
testcase_12 AC 35 ms
5,096 KB
testcase_13 AC 33 ms
5,096 KB
testcase_14 AC 35 ms
5,096 KB
testcase_15 AC 35 ms
5,092 KB
testcase_16 AC 34 ms
5,096 KB
testcase_17 AC 34 ms
5,096 KB
testcase_18 AC 35 ms
5,092 KB
testcase_19 AC 36 ms
5,100 KB
testcase_20 AC 35 ms
5,096 KB
testcase_21 AC 34 ms
5,092 KB
testcase_22 AC 35 ms
5,096 KB
testcase_23 AC 35 ms
5,096 KB
testcase_24 AC 36 ms
5,096 KB
testcase_25 AC 36 ms
5,092 KB
testcase_26 AC 37 ms
5,092 KB
testcase_27 AC 34 ms
5,100 KB
testcase_28 AC 35 ms
5,092 KB
testcase_29 AC 35 ms
5,092 KB
testcase_30 AC 35 ms
5,096 KB
testcase_31 AC 35 ms
5,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{Read, stdin};
use std::cmp::{max, min};

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];
                    }
                }
                continue;
            }
            if 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];
                    }
                }
                continue;
            }
            if lcount[l] % 2 != 0 {
                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];
                    }
                }
                continue;
            }
            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 min_out = n;
    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 out = min(min(i, j), n-(j+l));
            let mut cnt = 0;
            cnt += field[i][j];
            cnt += field[i][j+l-1];
            if cnt > 1 && out < min_out {
                min_out = out;
                sel_x = j;
                sel_y = i;
                hori = true;
            }
            let mut cnt = 0;
            cnt += field[j][i];
            cnt += field[j+l-1][i];
            if cnt > 1 && out < min_out {
                min_out = out;
                sel_x = i;
                sel_y = j;
                hori = false;
            }
        }
    }
    if min_out < n {
        Some((sel_x, sel_y, hori))
    } else {
        None
    }
}
0