結果

問題 No.5002 stick xor
ユーザー nebukuro09nebukuro09
提出日時 2018-05-26 14:14:08
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 987 ms / 1,000 ms
コード長 3,313 bytes
コンパイル時間 36,769 ms
実行使用メモリ 12,396 KB
スコア 43,137
最終ジャッジ日時 2023-06-01 00:00:00
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 986 ms
11,868 KB
testcase_01 AC 985 ms
12,124 KB
testcase_02 AC 985 ms
11,860 KB
testcase_03 AC 985 ms
11,868 KB
testcase_04 AC 985 ms
11,864 KB
testcase_05 AC 985 ms
12,132 KB
testcase_06 AC 985 ms
12,396 KB
testcase_07 AC 985 ms
12,388 KB
testcase_08 AC 985 ms
11,344 KB
testcase_09 AC 985 ms
11,608 KB
testcase_10 AC 985 ms
11,604 KB
testcase_11 AC 985 ms
11,608 KB
testcase_12 AC 986 ms
12,132 KB
testcase_13 AC 986 ms
11,872 KB
testcase_14 AC 987 ms
12,120 KB
testcase_15 AC 985 ms
11,608 KB
testcase_16 AC 986 ms
11,604 KB
testcase_17 AC 986 ms
11,868 KB
testcase_18 AC 985 ms
11,344 KB
testcase_19 AC 984 ms
11,592 KB
testcase_20 AC 985 ms
12,136 KB
testcase_21 AC 985 ms
12,120 KB
testcase_22 AC 985 ms
11,604 KB
testcase_23 AC 985 ms
11,344 KB
testcase_24 AC 986 ms
12,384 KB
testcase_25 AC 985 ms
11,872 KB
testcase_26 AC 986 ms
11,336 KB
testcase_27 AC 986 ms
10,816 KB
testcase_28 AC 985 ms
12,392 KB
testcase_29 AC 985 ms
10,812 KB
testcase_30 AC 986 ms
11,872 KB
testcase_31 AC 984 ms
11,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.datetime;

immutable int N = 60;
immutable int K = 500;

void main() {
    auto start_time = Clock.currTime();

    readln.split;
    auto X = readln.split.map!(to!int).array;
    auto A = N.iota.map!(_ => readln.chomp.map!(a => a == '1').array).array;
    int[][] ops = new int[][](K);

    int[] search(int x) {
        int best_score = -100;
        int[][] best_ops;

        foreach (i; 0..N) {
            int score = 0;
            foreach (j; 0..X[x]) {
                score += A[i][j] ? 1 : -1;
            }
            if (score > best_score) {
                best_score = score;
                best_ops = [[i, 0, i, X[x]-1]];
            } else if (score == best_score) {
                best_ops ~= [i, 0, i, X[x]-1];
            }
            foreach (j; 1..N-X[x]+1) {
                score += A[i][j-1] ? -1 : 1;
                score += A[i][j+X[x]-1] ? 1 : -1;
                if (score > best_score) {
                    best_score = score;
                    best_ops = [[i, j, i, j+X[x]-1]];
                } else if (score == best_score) {
                    best_ops ~= [i, j, i, j+X[x]-1];
                }
            }
        }

        foreach (j; 0..N) {
            int score = 0;
            foreach (i; 0..X[x]) {
                score += A[i][j] ? 1 : -1;
            }
            if (score > best_score) {
                best_score = score;
                best_ops = [[0, j, X[x]-1, j]];
            } else if (score == best_score) {
                best_ops ~= [0, j, X[x]-1, j];
            }
            foreach (i; 1..N-X[x]+1) {
                score += A[i-1][j] ? -1 : 1;
                score += A[i+X[x]-1][j] ? 1 : -1;
                if (score > best_score) {
                    best_score = score;
                    best_ops = [[i, j, i+X[x]-1, j]];
                } else if (score == best_score) {
                    best_ops ~= [i, j, i+X[x]-1, j];
                }
            }
        }

        return best_ops[uniform(0, best_ops.length)];
    }

    auto hoge = K.iota.array;
    hoge.randomShuffle;
    //hoge.sort!((a, b) => X[a] > X[b]);

    foreach (x; hoge) {
        ops[x] = search(x);
        foreach (i; ops[x][0]..ops[x][2]+1)
            foreach (j; ops[x][1]..ops[x][3]+1)
                A[i][j] ^= 1;
    }

    debug { int loop_cnt; int improved_cnt; }
    while ((Clock.currTime - start_time).total!"msecs" < dur!"msecs"(980).total!"msecs") {
        int x = uniform(0, K);
        debug { int score; }

        foreach (i; ops[x][0]..ops[x][2]+1)
            foreach (j; ops[x][1]..ops[x][3]+1) {
                debug { score += A[i][j] ? 1 : -1; }
                A[i][j] ^= 1;
            }

        ops[x] = search(x);

        foreach (i; ops[x][0]..ops[x][2]+1)
            foreach (j; ops[x][1]..ops[x][3]+1) {
                debug { score += A[i][j] ? 1 : -1; }
                A[i][j] ^= 1;
            }

        debug { loop_cnt += 1; if (score > 0) improved_cnt += 1; }
    }

    debug { writeln(improved_cnt, " / ", loop_cnt); }


    foreach (op; ops)
        op.map!(a => (a+1).to!string).join(" ").writeln;
}
0