結果

問題 No.5002 stick xor
コンテスト
ユーザー 最新の錆
提出日時 2018-05-31 00:16:26
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 3,873 bytes
コンパイル時間 4,765 ms
実行使用メモリ 5,108 KB
スコア 18,777
最終ジャッジ日時 2018-05-31 00:16:33
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 y in 0..n {
        for x in 0..n {
            if field[y][x] == 0 {
                continue;
            }
            let mut gs = vec![];
            let mut bs = vec![];
            let mut cnt_h = 1;
            let mut cnt_v = 1;
            for p in 1..lmax {
                if lcount[p+1] == 0 {
                    continue;
                }
                let l = 1+p as i32;
                if x+p < n {
                    cnt_h += field[y][x+p];
                    let value = -cnt_h * 100000 / l;
                    if cnt_h+cnt_h > l {
                        gs.push((value, p, true));
                    } else {
                        let value = lcount[p+1] as i32;
                        bs.push((-value, p, false));
                    }
                }
                if y+p < n {
                    cnt_v += field[y+p][x];
                    let value = -cnt_v * 100000 / l;
                    if cnt_v+cnt_v > l {
                        gs.push((value, p, false));
                    } else {
                        let value = lcount[p+1] as i32;
                        bs.push((-value, p, false));
                    }
                }
            }
            if !gs.is_empty() {
                gs.sort();
                if let Some((_, p, h)) = gs.pop() {
                    lcount[p+1] -= 1;
                    if h {
                        ans[p+1].push((y, x, y, x+p));
                        for x in x..x+p+1 {
                            field[y][x] = 1 - field[y][x];
                        }
                    } else {
                        ans[p+1].push((y, x, y+p, x));
                        for y in y..y+p+1 {
                            field[y][x] = 1 - field[y][x];
                        }
                    }
                }
            } else if !bs.is_empty() {
                bs.sort();
                if let Some((_, p, h)) = bs.pop() {
                    lcount[p+1] -= 1;
                    if h {
                        ans[p+1].push((y, x, y, x+p));
                        for x in x..x+p+1 {
                            field[y][x] = 1 - field[y][x];
                        }
                    } else {
                        ans[p+1].push((y, x, y+p, x));
                        for y in y..y+p+1 {
                            field[y][x] = 1 - field[y][x];
                        }
                    }
                }
            } else if lcount[1] > 0 {
                lcount[1] -= 1;
                ans[1].push((y, x, y, x));
                field[y][x] = 1 - field[y][x];
            }
        }
    }
    
    let mut emp = 0;
    for &l in ls.iter() {
        if let Some((y1, x1, y2, x2)) = ans[l].pop() {
            println!("{} {} {} {}", y1+1, x1+1, y2+1, x2+1);
        } else {
            println!("{} {} {} {}",
                n,
                n-l+1,
                n,
                n,
            );
            emp += 1;
        }
    }
    eprintln!("emp {}", emp);
}
0