結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 984 ms
3,168 KB
testcase_01 AC 983 ms
3,164 KB
testcase_02 AC 984 ms
3,164 KB
testcase_03 AC 984 ms
3,164 KB
testcase_04 AC 983 ms
3,164 KB
testcase_05 AC 984 ms
3,432 KB
testcase_06 AC 983 ms
3,164 KB
testcase_07 AC 983 ms
3,168 KB
testcase_08 AC 983 ms
3,168 KB
testcase_09 AC 983 ms
3,164 KB
testcase_10 AC 984 ms
3,168 KB
testcase_11 AC 984 ms
3,168 KB
testcase_12 AC 984 ms
2,900 KB
testcase_13 AC 982 ms
2,636 KB
testcase_14 AC 984 ms
3,164 KB
testcase_15 AC 984 ms
3,164 KB
testcase_16 AC 984 ms
3,168 KB
testcase_17 AC 984 ms
3,164 KB
testcase_18 AC 983 ms
3,164 KB
testcase_19 AC 984 ms
3,164 KB
testcase_20 AC 983 ms
3,164 KB
testcase_21 AC 984 ms
3,164 KB
testcase_22 AC 984 ms
3,164 KB
testcase_23 AC 984 ms
3,168 KB
testcase_24 AC 983 ms
3,164 KB
testcase_25 AC 984 ms
3,164 KB
testcase_26 AC 984 ms
3,164 KB
testcase_27 AC 984 ms
3,164 KB
testcase_28 AC 984 ms
3,168 KB
testcase_29 AC 984 ms
3,168 KB
testcase_30 AC 983 ms
3,164 KB
testcase_31 AC 984 ms
3,164 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_op = [-1, -1, -1, -1];

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

        foreach (j; 0..N) {
            foreach (i; 0..N-X[x]+1) {
                int score = 0;
                foreach (k; i..i+X[x]) {
                    score += A[k][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