結果

問題 No.5002 stick xor
ユーザー suikkeesuikkee
提出日時 2018-05-27 20:37:31
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 4,705 bytes
コンパイル時間 49,363 ms
スコア 0
最終ジャッジ日時 2018-05-27 20:38:33
ジャッジサーバーID
（参考情報） 		judge7 /
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.Scanner;
import java.util.SplittableRandom;

public class Main {
    private static long END_TIME = System.currentTimeMillis() + 950;

    private static Scanner in = new Scanner(System.in);

    private static int S, T;
    private static int[] L;
    private static int[] board;
    private static Rect[] rects;
    private static SplittableRandom rnd = new SplittableRandom("StickXor".hashCode());

    public static void main(String[] args) {
        init();
        putRandomly();
        improveSolution();
        printResult();
    }

    private static void init() {
        S = in.nextInt();
        T = in.nextInt();
        L = new int[T];
        for (int i = 0; i < T; i++) {
            L[i] = in.nextInt() - 1;
        }
        board = new int[S << 6];
        for (int y = 0; y < S; y++) {
            String line = in.next();
            for (int x = 0; x < S; x++) {
                board[p(x, y)] = line.charAt(x) - '0';
            }
        }
        rects = new Rect[T];
    }

    private static void improveSolution() {
        //END_TIME = System.currentTimeMillis() + 950;
        //int nIter = 0;
        while (System.currentTimeMillis() < END_TIME) {
            for (int t = 0; t < T; t++) {
                Rect rect = rects[t];
                revInRect(rect);
                int rLen = L[t];
                int rrLen = rLen + 1;
                int bestScore = Integer.MIN_VALUE;
                int bestSP = -1, bestEP = -1;
                for (int i = 0; i < S; i++) {
                    int sum0 = 0;
                    int sum1 = 0;
                    int tp0, tp1;
                    for (int j = 0; j < S; j++) {
                        sum0 += board[tp0 = p(i, j)];
                        sum1 += board[tp1 = p(j, i)];
                        if (j > rLen) {
                            sum0 -= board[tp0 - (rrLen << 6)];
                            sum1 -= board[tp1 - rrLen];
                            if (sum0 > bestScore) {
                                bestScore = sum0;
                                bestSP = tp0 - (rLen << 6);
                                bestEP = tp0;
                            }
                            else if (sum0 == bestScore && (rnd.nextInt() & 3) == 0) {
                                bestSP = tp0 - (rLen << 6);
                                bestEP = tp0;
                            }
                            if (sum1 > bestScore) {
                                bestScore = sum1;
                                bestSP = tp1 - rLen;
                                bestEP = tp1;
                            }
                            else if (sum1 == bestScore && (rnd.nextInt() & 3) == 0) {
                                bestSP = tp1 - rLen;
                                bestEP = tp1;
                            }
                        }
                    }
                }
                rect.p0 = bestSP;
                rect.p1 = bestEP;
                revInRect(rect);
            }
        }
    }

    private static void revInRect(Rect rect) {
        int x0 = x(rect.p0);
        int y0 = y(rect.p0);
        int x1 = x(rect.p1);
        int y1 = y(rect.p1);
        if (x0 == x1) {
            for (int y = y0; y <= y1; y++) {
                board[p(x0, y)] ^= 1;
            }
        }
        else {
            for (int x = x0; x <= x1; x++) {
                board[p(x, y0)] ^= 1;
            }
        }
    }

    private static void putRandomly() {
        for (int t = 0; t < T; t++ ) {
            int rLen = L[t];
            int sp0 = rnd.nextInt(S - rLen);
            int sp1 = rnd.nextInt(S);
            if ((rnd.nextInt() & 1) == 0) {
                rects[t] = new Rect(p(sp1, sp0), p(sp1, sp0 + rLen));
            }
            else {
                rects[t] = new Rect(p(sp0 ,sp1), p(sp0 + rLen, sp1));
            }
            revInRect(rects[t]);
        }
    }

    private static void printResult() {
        PrintWriter pw = new PrintWriter(System.out);
        for (Rect rect : rects) {
            int p0 = rect.p0;
            int x0 = x(p0) + 1;
            int y0 = y(p0) + 1;
            int p1 = rect.p1;
            int x1 = x(p1) + 1;
            int y1 = y(p1) + 1;
            pw.println(y0 + " " + x0 + " " + y1 + " " + x1);
        }
        pw.flush();
    }

    private static int p(int x, int y) { return y << 6 | x; }
    private static int x(int p) { return p & 0x3f; }
    private static int y(int p) { return p >> 6; }
    private static class Rect {
        int p0, p1;
        Rect(int p0, int p1) {
            this.p0 = p0;
            this.p1 = p1;
        }
    }
}
0