結果

問題 No.5002 stick xor
ユーザー suikkeesuikkee
提出日時 2018-05-28 01:20:34
言語 Java21
(openjdk 21)
結果
AC  
実行時間 893 ms / 1,000 ms
コード長 4,733 bytes
コンパイル時間 30,539 ms
実行使用メモリ 21,944 KB
スコア 43,583
最終ジャッジ日時 2018-05-28 01:21:06
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 873 ms
21,944 KB
testcase_01 AC 871 ms
21,876 KB
testcase_02 AC 807 ms
21,880 KB
testcase_03 AC 868 ms
21,916 KB
testcase_04 AC 836 ms
21,872 KB
testcase_05 AC 854 ms
21,940 KB
testcase_06 AC 893 ms
21,880 KB
testcase_07 AC 826 ms
21,876 KB
testcase_08 AC 854 ms
21,920 KB
testcase_09 AC 872 ms
21,876 KB
testcase_10 AC 809 ms
21,880 KB
testcase_11 AC 863 ms
21,876 KB
testcase_12 AC 845 ms
21,936 KB
testcase_13 AC 841 ms
21,940 KB
testcase_14 AC 862 ms
21,872 KB
testcase_15 AC 828 ms
21,876 KB
testcase_16 AC 865 ms
21,940 KB
testcase_17 AC 821 ms
21,872 KB
testcase_18 AC 855 ms
21,864 KB
testcase_19 AC 874 ms
21,876 KB
testcase_20 AC 826 ms
21,936 KB
testcase_21 AC 861 ms
21,848 KB
testcase_22 AC 825 ms
21,868 KB
testcase_23 AC 859 ms
21,876 KB
testcase_24 AC 841 ms
21,880 KB
testcase_25 AC 853 ms
21,936 KB
testcase_26 AC 820 ms
21,932 KB
testcase_27 AC 840 ms
21,876 KB
testcase_28 AC 867 ms
21,888 KB
testcase_29 AC 809 ms
21,868 KB
testcase_30 AC 864 ms
21,876 KB
testcase_31 AC 831 ms
21,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

public class Main {
    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 < 70; nIter++) {
            for (int t = 0; t < T; t++) {
                Rect rect;
                if (nIter == 0 ) {
                    rect = rects[t] = new Rect(-1, -1);
                }
                else {
                    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