#261518 (Rust) No.5002 stick xor

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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	49 ms; 5,100 KB
testcase_01	AC	53 ms; 5,100 KB
testcase_02	AC	53 ms; 5,096 KB
testcase_03	AC	42 ms; 5,096 KB
testcase_04	AC	49 ms; 5,100 KB
testcase_05	AC	42 ms; 5,100 KB
testcase_06	AC	51 ms; 5,100 KB
testcase_07	AC	41 ms; 5,096 KB
testcase_08	AC	44 ms; 5,100 KB
testcase_09	AC	50 ms; 5,100 KB
testcase_10	AC	52 ms; 5,100 KB
testcase_11	AC	52 ms; 5,100 KB
testcase_12	AC	46 ms; 5,096 KB
testcase_13	AC	47 ms; 5,100 KB
testcase_14	AC	52 ms; 5,096 KB
testcase_15	AC	42 ms; 5,100 KB
testcase_16	AC	47 ms; 5,100 KB
testcase_17	AC	38 ms; 5,100 KB
testcase_18	AC	44 ms; 5,100 KB
testcase_19	AC	39 ms; 5,096 KB
testcase_20	AC	37 ms; 5,100 KB
testcase_21	AC	44 ms; 5,100 KB
testcase_22	AC	51 ms; 5,096 KB
testcase_23	AC	41 ms; 5,096 KB
testcase_24	AC	51 ms; 5,096 KB
testcase_25	AC	42 ms; 5,100 KB
testcase_26	AC	64 ms; 5,100 KB
testcase_27	AC	55 ms; 5,100 KB
testcase_28	AC	78 ms; 5,100 KB
testcase_29	AC	65 ms; 5,096 KB
testcase_30	AC	52 ms; 5,096 KB
testcase_31	AC	39 ms; 5,096 KB

コンパイルメッセージ

warning: variable does not need to be mutable
   --> Main.rs:190:17
    |
190 |             let mut out = min(min(i, j), n-(j+l));
    |                 ---^^^^
    |                 |
    |                 help: remove this `mut`
    |
    = note: #[warn(unused_mut)] on by default

ソースコード

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 {
                let mut found = false;
                for w in 1..l-l/2 {
                    let w = l - w;
                    if let Some((x, y, h)) = search_side_w(n, &field, l, w) {
                        lcount[l] -= 2;
                        if h {
                            ans[l].push((x, y, h));
                            ans[l].push((x+w, y, h));
                            for p in 0..l+w {
                                if p < w || p >= l {
                                    field[y][x+p] = 1 - field[y][x+p];
                                }
                            }
                        } else {
                            ans[l].push((x, y, h));
                            ans[l].push((x, y+w, h));
                            for p in 0..l+w {
                                if p < w || p >= l {
                                    field[y+p][x] = 1 - field[y+p][x];
                                }
                            }
                        }
                        found = true;
                        break;
                    }
                }
                if found {
                    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 max_out = 0;
    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 out = min(min(i, j), n-(j+l));
            let mut cnt = 0;
            for p in j..j+l {
                cnt += field[i][p];
            }
            if cnt > max_cnt || (cnt == max_cnt && out > max_out) {
                max_cnt = cnt;
                max_out = out;
                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 || (cnt == max_cnt && out > max_out) {
                max_cnt = cnt;
                max_out = out;
                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 min_out = n as i32;
    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];
            let mut out = 0;
            for p in j+1..j+l-1 {
                out += field[i][p];
            }
            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];
            let mut out = 0;
            for p in j+1..j+l-1 {
                out += field[p][i];
            }
            if cnt > 1 && out < min_out {
                min_out = out;
                sel_x = i;
                sel_y = j;
                hori = false;
            }
        }
    }
    // if min_out < n {
    if min_out < n as i32 {
        Some((sel_x, sel_y, hori))
    } else {
        None
    }
}

fn search_side_w(n: usize, field: &Vec<Vec<i32>>, l: usize, w: usize) -> Option<(usize, usize, bool)> {
    let lw = l + w;
    let mut max_cnt = -1;
    let mut min_out = n as i32;
    let mut sel_x = 0;
    let mut sel_y = 0;
    let mut hori = false;
    for i in 0..n {
        for j in 0..n-lw+1 {
            let mut cnt = 0;
            let mut out = 0;
            for p in 0..lw {
                if p < w || p >= l {
                    cnt += field[i][j+p];
                } else {
                    out += field[i][j+p];
                }
            }
            if cnt+cnt > (w+w) as i32 && (
                    cnt > max_cnt || 
                    (cnt == max_cnt && out < min_out)) {
                max_cnt = cnt;
                min_out = out;
                sel_x = j;
                sel_y = i;
                hori = true;
            }
            let mut cnt = 0;
            let mut out = 0;
            for p in 0..lw {
                if p < w || p >= l {
                    cnt += field[j+p][i];
                } else {
                    out += field[j+p][i];
                }
            }
            if cnt+cnt > (w+w) as i32 && (
                    cnt > max_cnt || 
                    (cnt == max_cnt && out < min_out)) {
                max_cnt = cnt;
                min_out = out;
                sel_x = i;
                sel_y = j;
                hori = false;
            }
        }
    }
    if max_cnt < 0 {
        None
    } else {
        Some((sel_x, sel_y, hori))
    }
}