結果

問題 No.5002 stick xor
ユーザー nebukuro09
提出日時 2018-05-26 08:45:31
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 987 ms / 1,000 ms
コード長 2,558 bytes
コンパイル時間 37,338 ms
実行使用メモリ 9,244 KB
スコア 41,155
最終ジャッジ日時 2023-06-01 00:00:00
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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_op = [-1, -1, -1, -1];

        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_op = [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_op = [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_op = [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_op = [i, j, i+X[x]-1, j];
                }
            }
        }

        return best_op;
    }

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

    while ((Clock.currTime - start_time).total!"msecs" < dur!"msecs"(980).total!"msecs") {
        int x = uniform(0, K);
        foreach (i; ops[x][0]..ops[x][2]+1)
            foreach (j; ops[x][1]..ops[x][3]+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)
                A[i][j] ^= 1;
    }


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