#261730 (Rust) No.5002 stick xor

提出ソース

結果

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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 5,108 KB
testcase_01	AC	8 ms 5,104 KB
testcase_02	AC	7 ms 5,108 KB
testcase_03	AC	7 ms 5,108 KB
testcase_04	AC	8 ms 5,108 KB
testcase_05	AC	8 ms 5,108 KB
testcase_06	AC	8 ms 5,108 KB
testcase_07	AC	7 ms 5,108 KB
testcase_08	AC	7 ms 5,104 KB
testcase_09	AC	8 ms 5,108 KB
testcase_10	AC	8 ms 5,108 KB
testcase_11	AC	7 ms 5,108 KB
testcase_12	AC	8 ms 5,104 KB
testcase_13	AC	10 ms 5,104 KB
testcase_14	AC	8 ms 5,104 KB
testcase_15	AC	9 ms 5,104 KB
testcase_16	AC	8 ms 5,108 KB
testcase_17	AC	7 ms 5,104 KB
testcase_18	AC	8 ms 5,108 KB
testcase_19	AC	7 ms 5,108 KB
testcase_20	AC	8 ms 5,108 KB
testcase_21	AC	7 ms 5,108 KB
testcase_22	AC	8 ms 5,104 KB
testcase_23	AC	7 ms 5,104 KB
testcase_24	AC	7 ms 5,104 KB
testcase_25	AC	8 ms 5,108 KB
testcase_26	AC	8 ms 5,108 KB
testcase_27	AC	8 ms 5,108 KB
testcase_28	AC	8 ms 5,108 KB
testcase_29	AC	8 ms 5,108 KB
testcase_30	AC	7 ms 5,108 KB
testcase_31	AC	8 ms 5,108 KB

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

ソースコード

raw source code

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 idx = vec![];
    for y in 0..n {
        for x in 0..n {
            idx.push((y, x));
        }
    }
    macro_rules! shuffle { () => {
        for i in 0..idx.len() {
            let (y, x) = idx[i];
            if field[y][x] != 0 {
                let j = (i + ls[i % ls.len()]) % idx.len();
                idx.swap(i, j);
            }
        }
        for i in 0..idx.len() {
            let (y, x) = idx[i];
            if field[y][x] == 0 {
                let j = (i + ls[i % ls.len()]) % idx.len();
                idx.swap(i, j);
            }
        }
    }}
    
    shuffle!();
    
    let mut ans = vec![vec![]; lmax+1];
    
    loop {
        let mut changes = 0;
        for &(y, x) in idx.iter() {
            if field[y][x] == 0 {
                continue;
            }
            let mut gs = vec![];
            let mut cnt_h = 1;
            let mut cnt_v = 1;
            for p in 10..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));
                    }
                }
                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));
                    }
                }
            }
            if !gs.is_empty() {
                changes += 1;
                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];
                        }
                    }
                }
            }
        }
        if changes == 0 {
            break;
        }
    }
    
    shuffle!();
    
    loop {
        let mut changes = 0;
        for &(y, x) in idx.iter() {
            if field[y][x] == 0 {
                continue;
            }
            let mut gs = vec![];
            let mut cnt_h = 1;
            let mut cnt_v = 1;
            for p in 4..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));
                    }
                }
                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));
                    }
                }
            }
            if !gs.is_empty() {
                changes += 1;
                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];
                        }
                    }
                }
            }
        }
        if changes == 0 {
            break;
        }
    }
    
    shuffle!();

    loop {
        let mut changes = 0;
        for &(y, x) in idx.iter() {
            if field[y][x] == 0 {
                continue;
            }
            let mut gs = 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));
                    }
                }
                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));
                    }
                }
            }
            if !gs.is_empty() {
                changes += 1;
                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];
                        }
                    }
                }
            }
        }
        if changes == 0 {
            break;
        }
    }
    
    shuffle!();

    loop {
        let mut changes = 0;
        for &(y, x) in idx.iter() {
            if field[y][x] == 0 {
                continue;
            }
            let mut gs = 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;
                    gs.push((value, p, true));
                }
                if y+p < n {
                    cnt_v += field[y+p][x];
                    let value = -cnt_v * 100000 / l;
                    gs.push((value, p, false));
                }
            }
            if !gs.is_empty() {
                changes += 1;
                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];
                        }
                    }
                }
            }
        }
        if changes == 0 {
            break;
        }
    }
    
    shuffle!();
    
    loop {
        let mut changes = 0;
        for &(y, x) in idx.iter() {
            if field[y][x] == 0 {
                continue;
            }
            let mut gs = vec![];
            let mut cnt_h = 1;
            let mut cnt_v = 1;
            for p in 0..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;
                    gs.push((value, p, true));
                }
                if y+p < n {
                    cnt_v += field[y+p][x];
                    let value = -cnt_v * 100000 / l;
                    gs.push((value, p, false));
                }
            }
            if !gs.is_empty() {
                changes += 1;
                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];
                        }
                    }
                }
            }
        }
        if changes == 0 {
            break;
        }
    }
    
    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);
}

yukicoder

結果

テストケース

ソースコード