結果

問題 No.5002 stick xor
ユーザー suikkeesuikkee
提出日時 2018-05-27 20:30:24
言語 Java21
(openjdk 21)
結果
AC  
実行時間 244 ms / 1,000 ms
コード長 4,188 bytes
コンパイル時間 9,249 ms
実行使用メモリ 21,948 KB
スコア 36,963
最終ジャッジ日時 2018-05-27 20:30:35
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 191 ms
21,732 KB
testcase_01 AC 216 ms
21,920 KB
testcase_02 AC 229 ms
21,768 KB
testcase_03 AC 194 ms
21,724 KB
testcase_04 AC 193 ms
21,724 KB
testcase_05 AC 191 ms
21,728 KB
testcase_06 AC 190 ms
21,728 KB
testcase_07 AC 217 ms
21,728 KB
testcase_08 AC 219 ms
21,920 KB
testcase_09 AC 225 ms
21,948 KB
testcase_10 AC 191 ms
21,796 KB
testcase_11 AC 189 ms
21,724 KB
testcase_12 AC 189 ms
21,716 KB
testcase_13 AC 190 ms
21,724 KB
testcase_14 AC 189 ms
21,728 KB
testcase_15 AC 244 ms
21,924 KB
testcase_16 AC 190 ms
21,720 KB
testcase_17 AC 190 ms
21,724 KB
testcase_18 AC 201 ms
21,936 KB
testcase_19 AC 191 ms
21,728 KB
testcase_20 AC 201 ms
21,936 KB
testcase_21 AC 211 ms
21,920 KB
testcase_22 AC 228 ms
21,936 KB
testcase_23 AC 190 ms
21,728 KB
testcase_24 AC 190 ms
21,724 KB
testcase_25 AC 189 ms
21,724 KB
testcase_26 AC 189 ms
21,728 KB
testcase_27 AC 189 ms
21,732 KB
testcase_28 AC 230 ms
21,924 KB
testcase_29 AC 201 ms
21,912 KB
testcase_30 AC 188 ms
21,724 KB
testcase_31 AC 189 ms
21,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

public class Main {
    private static final 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() {
        for (int nIter = 0; nIter < 5; nIter++) {
            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;
                            }
                            if (sum1 > bestScore) {
                                bestScore = sum1;
                                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