#261516 (Rust) No.5002 stick xor

提出ソース

結果

問題	No.5002 stick xor
ユーザー	最新の錆
提出日時	2018-05-30 06:55:11
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	37 ms / 1,000 ms
コード長	7,067 bytes
コンパイル時間	3,480 ms
実行使用メモリ	5,100 KB
スコア	40,139
最終ジャッジ日時	2018-05-30 06:55:17
ジャッジサーバーID （参考情報）	judge6 /
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

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

権限があれば一括ダウンロードができます

コンパイルメッセージ

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード