結果
問題 | No.5002 stick xor |
ユーザー | EvbCFfp1XB |
提出日時 | 2018-05-27 22:29:56 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 941 ms / 1,000 ms |
コード長 | 13,826 bytes |
コンパイル時間 | 34,096 ms |
実行使用メモリ | 22,540 KB |
スコア | 48,093 |
最終ジャッジ日時 | 2018-05-27 22:30:33 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 929 ms
22,516 KB |
testcase_01 | AC | 929 ms
22,516 KB |
testcase_02 | AC | 929 ms
22,520 KB |
testcase_03 | AC | 930 ms
22,516 KB |
testcase_04 | AC | 934 ms
22,524 KB |
testcase_05 | AC | 941 ms
22,540 KB |
testcase_06 | AC | 933 ms
22,512 KB |
testcase_07 | AC | 933 ms
22,520 KB |
testcase_08 | AC | 936 ms
22,524 KB |
testcase_09 | AC | 929 ms
22,512 KB |
testcase_10 | AC | 928 ms
22,512 KB |
testcase_11 | AC | 936 ms
22,524 KB |
testcase_12 | AC | 929 ms
22,520 KB |
testcase_13 | AC | 930 ms
22,524 KB |
testcase_14 | AC | 929 ms
22,528 KB |
testcase_15 | AC | 928 ms
22,512 KB |
testcase_16 | AC | 927 ms
22,512 KB |
testcase_17 | AC | 930 ms
22,520 KB |
testcase_18 | AC | 929 ms
22,516 KB |
testcase_19 | AC | 928 ms
22,516 KB |
testcase_20 | AC | 928 ms
22,512 KB |
testcase_21 | AC | 930 ms
22,520 KB |
testcase_22 | AC | 929 ms
22,516 KB |
testcase_23 | AC | 929 ms
22,516 KB |
testcase_24 | AC | 928 ms
22,508 KB |
testcase_25 | AC | 930 ms
22,524 KB |
testcase_26 | AC | 928 ms
22,512 KB |
testcase_27 | AC | 930 ms
22,512 KB |
testcase_28 | AC | 928 ms
22,520 KB |
testcase_29 | AC | 929 ms
22,520 KB |
testcase_30 | AC | 928 ms
22,516 KB |
testcase_31 | AC | 927 ms
22,516 KB |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { String line = br.readLine(); String[] split = line.split(" "); int N = Integer.parseInt(split[0]); int K = Integer.parseInt(split[1]); line = br.readLine(); split = line.split(" "); int[] L = new int[K]; for (int i = 0; i < K; i++) { L[i] = Integer.parseInt(split[i]); } int[][] A = new int[N][N]; for (int r = 0; r < N; r++) { line = br.readLine(); for (int c = 0; c < N; c++) { A[r][c] = line.charAt(c) - '0'; } } String ret = new Main().run(N, K, L, A); System.out.println(ret); System.out.flush(); } catch (Exception e) { e.printStackTrace(); } } private double score; private double bestScore; static final Watch watch = new Watch(); static final XorShift rng = new XorShift(System.nanoTime()); private SAState sa = new SAState(); private int N; private int K; private int[] L; private int[][] A; private int W0; private boolean[] isVerticals; private int[] rs; private int[] cs; private boolean[] bestIsVerticals; private int[] bestRs; private int[] bestCs; private String run(int N, int K, int[] L, int[][] A) { init(N, K, L, A); greedy(); SA(); return makeSolution(); } private void init(int n, int k, int[] l, int[][] a) { N = n; K = k; L = l; A = a; isVerticals = new boolean[K]; rs = new int[K]; cs = new int[K]; bestIsVerticals = new boolean[K]; bestRs = new int[K]; bestCs = new int[K]; W0 = 0; W0 = calculateScore(a); Utils.debug("init", "time", watch.getSecondString()); } private void greedy() { for (int k = 0; k < K; k++) { isVerticals[k] = rng.nextDouble() < 0.5; if (isVerticals[k]) { rs[k] = (int) ((N - L[k]) * rng.nextDouble()); cs[k] = (int) (N * rng.nextDouble()); } else { rs[k] = (int) (N * rng.nextDouble()); cs[k] = (int) ((N - L[k]) * rng.nextDouble()); } flip(k, isVerticals[k], rs[k], cs[k]); } } private void SA() { score = calculateScore(A); bestScore = -1e99; saveBest(); sa.init(); for (;; sa.numIterations++) { if ((sa.numIterations & ((1 << 10) - 1)) == 0) { sa.update(); if (sa.isTLE()) { loadBest(); Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature)); break; } } mutate(); } Utils.debug("SA", "time", watch.getSecondString()); } private void mutate() { int random = (int) (2 * rng.nextDouble()); if (random == 0) { random(); } else { swap(); } } private void random() { int k = (int) (K * rng.nextDouble()); boolean newIsVertical = rng.nextDouble() < 0.5; int newR = rs[k] + (int) (-sa.range * 0.5 + sa.range * rng.nextDouble()); int newC = cs[k] + (int) (-sa.range * 0.5 + sa.range * rng.nextDouble()); if (newIsVertical) { newR = Math.min(Math.max(newR, 0), N - L[k] - 1); newC = Math.min(Math.max(newC, 0), N - 1); } else { newR = Math.min(Math.max(newR, 0), N - 1); newC = Math.min(Math.max(newC, 0), N - L[k] - 1); } double deltaScore = 0; if (isVerticals[k]) { for (int l = 0; l < L[k]; l++) { if (A[rs[k] + l][cs[k]] == 0) { deltaScore--; } else { deltaScore++; } } } else { for (int l = 0; l < L[k]; l++) { if (A[rs[k]][cs[k] + l] == 0) { deltaScore--; } else { deltaScore++; } } } if (newIsVertical) { for (int l = 0; l < L[k]; l++) { if (isIntersect(newR + l, newC, rs[k], cs[k], rs[k] + (isVerticals[k] ? L[k] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k] - 1))) { if (A[newR + l][newC] == 0) { deltaScore++; } else { deltaScore--; } } else { if (A[newR + l][newC] == 1) { deltaScore++; } else { deltaScore--; } } } } else { for (int l = 0; l < L[k]; l++) { if (isIntersect(newR, newC + l, rs[k], cs[k], rs[k] + (isVerticals[k] ? L[k] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k] - 1))) { if (A[newR][newC + l] == 0) { deltaScore++; } else { deltaScore--; } } else { if (A[newR][newC + l] == 1) { deltaScore++; } else { deltaScore--; } } } } if (sa.accept(deltaScore)) { score += deltaScore; flip(k, isVerticals[k], rs[k], cs[k]); isVerticals[k] = newIsVertical; rs[k] = newR; cs[k] = newC; flip(k, isVerticals[k], rs[k], cs[k]); saveBest(); } else { } } private void swap() { int k = (int) (K * rng.nextDouble()); int k2 = (int) ((K - 1) * rng.nextDouble()); if (k2 >= k) { k2++; } if (L[k] == L[k2]) { return; } if (L[k] > L[k2]) { if (isVerticals[k2]) { if (rs[k2] + L[k] >= N) { return; } } else { if (cs[k2] + L[k] >= N) { return; } } } else { if (isVerticals[k]) { if (rs[k] + L[k2] >= N) { return; } } else { if (cs[k] + L[k2] >= N) { return; } } } double deltaScore = 0; if (L[k] > L[k2]) { if (isVerticals[k]) { for (int l = L[k2]; l < L[k]; l++) { if (A[rs[k] + l][cs[k]] == 0) { deltaScore--; } else { deltaScore++; } } } else { for (int l = L[k2]; l < L[k]; l++) { if (A[rs[k]][cs[k] + l] == 0) { deltaScore--; } else { deltaScore++; } } } if (isVerticals[k2]) { for (int l = L[k2]; l < L[k]; l++) { if (isIntersect(rs[k2] + l, cs[k2], rs[k] + (isVerticals[k] ? L[k2] : 0), cs[k] + (isVerticals[k] ? 0 : L[k2]), rs[k] + (isVerticals[k] ? L[k] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k] - 1))) { if (A[rs[k2] + l][cs[k2]] == 1) { deltaScore--; } else { deltaScore++; } } else { if (A[rs[k2] + l][cs[k2]] == 0) { deltaScore--; } else { deltaScore++; } } } } else { for (int l = L[k2]; l < L[k]; l++) { if (isIntersect(rs[k2], cs[k2] + l, rs[k] + (isVerticals[k] ? L[k2] : 0), cs[k] + (isVerticals[k] ? 0 : L[k2]), rs[k] + (isVerticals[k] ? L[k] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k] - 1))) { if (A[rs[k2]][cs[k2] + l] == 1) { deltaScore--; } else { deltaScore++; } } else { if (A[rs[k2]][cs[k2] + l] == 0) { deltaScore--; } else { deltaScore++; } } } } } else { if (isVerticals[k]) { for (int l = L[k]; l < L[k2]; l++) { if (A[rs[k] + l][cs[k]] == 0) { deltaScore--; } else { deltaScore++; } } } else { for (int l = L[k]; l < L[k2]; l++) { if (A[rs[k]][cs[k] + l] == 0) { deltaScore--; } else { deltaScore++; } } } if (isVerticals[k2]) { for (int l = L[k]; l < L[k2]; l++) { if (isIntersect(rs[k2] + l, cs[k2], rs[k] + (isVerticals[k] ? L[k] : 0), cs[k] + (isVerticals[k] ? 0 : L[k]), rs[k] + (isVerticals[k] ? L[k2] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k2] - 1))) { if (A[rs[k2] + l][cs[k2]] == 1) { deltaScore--; } else { deltaScore++; } } else { if (A[rs[k2] + l][cs[k2]] == 0) { deltaScore--; } else { deltaScore++; } } } } else { for (int l = L[k]; l < L[k2]; l++) { if (isIntersect(rs[k2], cs[k2] + l, rs[k] + (isVerticals[k] ? L[k] : 0), cs[k] + (isVerticals[k] ? 0 : L[k]), rs[k] + (isVerticals[k] ? L[k2] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k2] - 1))) { if (A[rs[k2]][cs[k2] + l] == 1) { deltaScore--; } else { deltaScore++; } } else { if (A[rs[k2]][cs[k2] + l] == 0) { deltaScore--; } else { deltaScore++; } } } } } if (sa.accept(deltaScore)) { score += deltaScore; flip(k, isVerticals[k], rs[k], cs[k]); flip(k2, isVerticals[k2], rs[k2], cs[k2]); { boolean swap = isVerticals[k]; isVerticals[k] = isVerticals[k2]; isVerticals[k2] = swap; } { int swap = rs[k]; rs[k] = rs[k2]; rs[k2] = swap; swap = cs[k]; cs[k] = cs[k2]; cs[k2] = swap; } flip(k, isVerticals[k], rs[k], cs[k]); flip(k2, isVerticals[k2], rs[k2], cs[k2]); saveBest(); } else { } } private String makeSolution() { StringBuilder result = new StringBuilder(); for (int k = 0; k < K; k++) { if (isVerticals[k]) { result.append("" + (rs[k] + 1) + " " + (cs[k] + 1) + " " + (rs[k] + 1 + (L[k] - 1)) + " " + (cs[k] + 1) + "\n"); } else { result.append("" + (rs[k] + 1) + " " + (cs[k] + 1) + " " + (rs[k] + 1) + " " + (cs[k] + 1 + (L[k] - 1)) + "\n"); } } return result.toString(); } private boolean isIntersect(int r, int c, int minR, int minC, int maxR, int maxC) { return r >= minR && r <= maxR && c >= minC && c <= maxC; } private void flip(int k, boolean isVertical, int r, int c) { if (isVertical) { for (int l = 0; l < L[k]; l++) { A[r + l][c] ^= 1; } } else { for (int l = 0; l < L[k]; l++) { A[r][c + l] ^= 1; } } } private int calculateScore(int[][] a) { int W = 0; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (a[r][c] == 0) { W++; } } } return W - W0; } private void saveBest() { if (score > bestScore) { bestScore = score; for (int k = 0; k < K; k++) { bestIsVerticals[k] = isVerticals[k]; bestRs[k] = rs[k]; bestCs[k] = cs[k]; } } } private void loadBest() { score = bestScore; for (int k = 0; k < K; k++) { isVerticals[k] = bestIsVerticals[k]; rs[k] = bestRs[k]; cs[k] = bestCs[k]; } } } class SAState { public static final boolean useTime = true; public double startTime = 0; public double endTime = 0.85; public double time = startTime; public double startTemperature = 1; public double endTemperature = 0; public double inverseTemperature = 1.0 / startTemperature; public double lastAcceptTemperature = startTemperature; public double startRange = 31; public double endRange = 3; public double range = startRange; public int numIterations; public int validIterations; public int acceptIterations; public void init() { numIterations = 0; validIterations = 0; acceptIterations = 0; startTime = useTime ? Main.watch.getSecond() : numIterations; update(); lastAcceptTemperature = inverseTemperature; } public void update() { updateTime(); updateTemperature(); updateRange(); } public void updateTemperature() { inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0)); } public void updateRange() { range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0); } public void updateTime() { time = useTime ? Main.watch.getSecond() : numIterations; } public boolean isTLE() { return time >= endTime; } public boolean accept(double deltaScore) { return acceptB(deltaScore); } public boolean acceptB(double deltaScore) { validIterations++; if (deltaScore > -1e-9) { acceptIterations++; return true; } assert deltaScore < 0; assert 1.0 / inverseTemperature >= 0; if (deltaScore * inverseTemperature < -10) { return false; } if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } public boolean acceptS(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } assert deltaScore > 0; assert 1.0 / inverseTemperature >= 0; if (-deltaScore * inverseTemperature < -10) { return false; } if (Main.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } } final class Utils { private Utils() { } public static final void debug(Object... o) { System.err.println(toString(o)); } public static final String toString(Object... o) { return Arrays.deepToString(o); } } class Watch { private long start; public Watch() { init(); } public double getSecond() { return (System.nanoTime() - start) * 1e-9; } public void init() { init(System.nanoTime()); } private void init(long start) { this.start = start; } public String getSecondString() { return toString(getSecond()); } public static final String toString(double second) { if (second < 60) { return String.format("%5.2fs", second); } else if (second < 60 * 60) { int minute = (int) (second / 60); return String.format("%2dm%2ds", minute, (int) (second % 60)); } else { int hour = (int) (second / (60 * 60)); int minute = (int) (second / 60); return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60)); } } } class XorShift { private int w = 88675123; private int x = 123456789; private int y = 362436069; private int z = 521288629; public XorShift(long l) { x = (int) l; } public int nextInt() { final int t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >>> 19) ^ (t ^ (t >>> 8)); return w; } public long nextLong() { return ((long) nextInt() << 32) ^ (long) nextInt(); } public double nextDouble() { return (nextInt() >>> 1) * 4.6566128730773926E-10; } public int nextInt(int n) { return (int) (n * nextDouble()); } }