#260927 (Java) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: suikkee
• 提出日時: 2018-05-27 21:19:10
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 908 ms / 1,000 ms
• コード長: 4,551 bytes
• コンパイル時間: 31,237 ms
• 実行使用メモリ: 21,952 KB
• スコア: 42,583
• 最終ジャッジ日時: 2018-05-27 21:19:47
• ジャッジサーバーID （参考情報）: judge6 /

ファイルパターン	結果
other	AC * 32

ソースコード

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