結果
問題 | No.5014 セクスタプル (reactive) |
ユーザー | EvbCFfp1XB |
提出日時 | 2022-12-29 18:26:15 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 848 ms / 2,000 ms |
コード長 | 14,843 bytes |
コンパイル時間 | 2,256 ms |
実行使用メモリ | 74,472 KB |
スコア | 184,043,694 |
平均クエリ数 | 35.00 |
最終ジャッジ日時 | 2022-12-29 18:27:44 |
合計ジャッジ時間 | 86,180 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 753 ms
72,860 KB |
testcase_01 | AC | 751 ms
73,276 KB |
testcase_02 | AC | 735 ms
71,840 KB |
testcase_03 | AC | 783 ms
74,472 KB |
testcase_04 | AC | 787 ms
73,356 KB |
testcase_05 | AC | 743 ms
73,584 KB |
testcase_06 | AC | 779 ms
73,944 KB |
testcase_07 | AC | 748 ms
73,428 KB |
testcase_08 | AC | 760 ms
72,324 KB |
testcase_09 | AC | 753 ms
73,344 KB |
testcase_10 | AC | 752 ms
73,440 KB |
testcase_11 | AC | 734 ms
73,180 KB |
testcase_12 | AC | 788 ms
73,736 KB |
testcase_13 | AC | 744 ms
71,372 KB |
testcase_14 | AC | 741 ms
71,732 KB |
testcase_15 | AC | 762 ms
72,968 KB |
testcase_16 | AC | 746 ms
73,876 KB |
testcase_17 | AC | 848 ms
71,684 KB |
testcase_18 | AC | 758 ms
72,948 KB |
testcase_19 | AC | 748 ms
73,416 KB |
testcase_20 | AC | 739 ms
74,148 KB |
testcase_21 | AC | 758 ms
73,888 KB |
testcase_22 | AC | 778 ms
72,116 KB |
testcase_23 | AC | 745 ms
73,260 KB |
testcase_24 | AC | 760 ms
72,984 KB |
testcase_25 | AC | 745 ms
71,572 KB |
testcase_26 | AC | 757 ms
73,156 KB |
testcase_27 | AC | 768 ms
73,060 KB |
testcase_28 | AC | 765 ms
72,604 KB |
testcase_29 | AC | 786 ms
73,968 KB |
testcase_30 | AC | 761 ms
73,448 KB |
testcase_31 | AC | 748 ms
73,220 KB |
testcase_32 | AC | 751 ms
73,172 KB |
testcase_33 | AC | 755 ms
73,240 KB |
testcase_34 | AC | 801 ms
73,376 KB |
testcase_35 | AC | 737 ms
72,340 KB |
testcase_36 | AC | 764 ms
73,472 KB |
testcase_37 | AC | 752 ms
74,056 KB |
testcase_38 | AC | 746 ms
73,320 KB |
testcase_39 | AC | 781 ms
74,204 KB |
testcase_40 | AC | 750 ms
72,908 KB |
testcase_41 | AC | 769 ms
73,336 KB |
testcase_42 | AC | 764 ms
73,664 KB |
testcase_43 | AC | 738 ms
71,308 KB |
testcase_44 | AC | 770 ms
73,808 KB |
testcase_45 | AC | 761 ms
73,852 KB |
testcase_46 | AC | 750 ms
73,148 KB |
testcase_47 | AC | 809 ms
73,900 KB |
testcase_48 | AC | 760 ms
73,920 KB |
testcase_49 | AC | 797 ms
71,860 KB |
testcase_50 | AC | 752 ms
73,260 KB |
testcase_51 | AC | 776 ms
71,836 KB |
testcase_52 | AC | 746 ms
71,840 KB |
testcase_53 | AC | 758 ms
73,328 KB |
testcase_54 | AC | 782 ms
73,040 KB |
testcase_55 | AC | 745 ms
73,116 KB |
testcase_56 | AC | 779 ms
73,076 KB |
testcase_57 | AC | 744 ms
73,412 KB |
testcase_58 | AC | 770 ms
72,960 KB |
testcase_59 | AC | 765 ms
72,972 KB |
testcase_60 | AC | 758 ms
73,856 KB |
testcase_61 | AC | 761 ms
71,368 KB |
testcase_62 | AC | 745 ms
74,436 KB |
testcase_63 | AC | 776 ms
73,108 KB |
testcase_64 | AC | 745 ms
73,680 KB |
testcase_65 | AC | 768 ms
74,188 KB |
testcase_66 | AC | 760 ms
72,808 KB |
testcase_67 | AC | 756 ms
73,372 KB |
testcase_68 | AC | 782 ms
73,272 KB |
testcase_69 | AC | 747 ms
73,628 KB |
testcase_70 | AC | 779 ms
73,360 KB |
testcase_71 | AC | 757 ms
73,632 KB |
testcase_72 | AC | 794 ms
73,236 KB |
testcase_73 | AC | 766 ms
73,208 KB |
testcase_74 | AC | 758 ms
73,344 KB |
testcase_75 | AC | 784 ms
73,708 KB |
testcase_76 | AC | 757 ms
74,260 KB |
testcase_77 | AC | 787 ms
73,644 KB |
testcase_78 | AC | 746 ms
73,264 KB |
testcase_79 | AC | 769 ms
71,976 KB |
testcase_80 | AC | 758 ms
73,048 KB |
testcase_81 | AC | 845 ms
73,332 KB |
testcase_82 | AC | 783 ms
73,296 KB |
testcase_83 | AC | 742 ms
73,156 KB |
testcase_84 | AC | 772 ms
73,908 KB |
testcase_85 | AC | 745 ms
73,044 KB |
testcase_86 | AC | 753 ms
73,712 KB |
testcase_87 | AC | 782 ms
73,696 KB |
testcase_88 | AC | 745 ms
73,652 KB |
testcase_89 | AC | 770 ms
71,256 KB |
testcase_90 | AC | 739 ms
72,080 KB |
testcase_91 | AC | 777 ms
72,692 KB |
testcase_92 | AC | 755 ms
72,192 KB |
testcase_93 | AC | 754 ms
71,664 KB |
testcase_94 | AC | 751 ms
73,544 KB |
testcase_95 | AC | 729 ms
71,900 KB |
testcase_96 | AC | 785 ms
73,212 KB |
testcase_97 | AC | 747 ms
73,212 KB |
testcase_98 | AC | 768 ms
72,200 KB |
testcase_99 | AC | 743 ms
73,060 KB |
ソースコード
import java.util.Arrays; import java.util.Scanner; public class Main { private int[][] dice; private int[][] table; private int[] counts = new int[6]; private SAState sa = new SAState(); private int score; private int copyIndex; private int[][] copyTable; private int[][] counts_row = new int[6][6]; private int[][] counts_column = new int[6][6]; private int[] part_score_row = new int[6]; private int[] part_score_column = new int[6]; public static void main(String[] args) throws Exception { new Main().run(); } private void run() { solve(); } private void solve() { try (final Scanner in = new Scanner(System.in)) { table = new int[6][6]; for (int r = 0; r < 6; r++) { Arrays.fill(table[r], -1); } dice = new int[36][6]; for (int i = 0; i < 36; i++) { for (int j = 0; j < 6; j++) { dice[i][j] = Constants.RNG.nextInt(6); } } for (int index = 0; index < 35; index++) { for (int j = 0; j < 6; j++) { dice[index][j] = in.nextInt() - 1; if (index == 0 && j == 0) { Constants.watch.init(); } } copyIndex = index; copyTable = copy(table); { int index2 = index; for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { if (copyTable[r][c] < 0) { copyTable[r][c] = index2++; } } } } score = calculateScore2(); multiSA(); int bestR = -1; int bestC = -1; for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { if (copyTable[r][c] == index) { bestR = r; bestC = c; } } } Utils.debug(score); table[bestR][bestC] = index; System.out.println((bestR + 1) + " " + (bestC + 1)); System.out.flush(); } } catch (Exception e) { e.printStackTrace(); } } private int[][] copy(int[][] table) { int[][] copy = new int[6][6]; for (int r = 0; r < 6; r++) { for (int c = 0; c < 6; c++) { copy[r][c] = table[r][c]; } } return copy; } private void multiSA() { int numRestart = 1; double startTime = 0; double endTime = 5e4; double remainTime = endTime - startTime; double startStartTemperature = 1; double endStartTemperature = 1e-9; for (double restart = 0; restart < numRestart; restart++) { sa.startTime = startTime + remainTime * restart / numRestart; sa.endTime = startTime + remainTime * (restart + 1) / numRestart; sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart); sa.endTemperature = 1e-9; SA(); } } private void SA() { sa.init(); for (;; ++sa.numIterations) { if ((sa.numIterations & ((1 << 7) - 1)) == 0) { sa.update(); if (sa.isTLE()) { break; } } mutate(); } } private void mutate() { change(); } private void change() { int v1 = sa.numIterations % 36; int r1 = v1 / 6; int c1 = v1 % 6; if (copyTable[r1][c1] < copyIndex) { return; } int r2 = Constants.RNG.nextInt(6); int c2 = Constants.RNG.nextInt(6); while ((r2 == r1 && c2 == c1) || (copyTable[r2][c2] < copyIndex)) { r2 = Constants.RNG.nextInt(6); c2 = Constants.RNG.nextInt(6); } int current1 = copyTable[r1][c1]; int current2 = copyTable[r2][c2]; int before = 0; before += part_score_row[r1]; before += part_score_row[r2]; before += part_score_column[c1]; before += part_score_column[c2]; copyTable[r1][c1] = current2; copyTable[r2][c2] = current1; int after_r1 = partScoreRow(counts_row, r1); int after_r2 = partScoreRow(counts_row, r2); int after_c1 = partScoreColumn(counts_column, c1); int after_c2 = partScoreColumn(counts_column, c2); int after = 0; after += after_r1; after += after_r2; after += after_c1; after += after_c2; int deltaScore = after - before; if (sa.accept(deltaScore)) { score += deltaScore; part_score_row[r1] = after_r1; part_score_row[r2] = after_r2; part_score_column[c1] = after_c1; part_score_column[c2] = after_c2; } else { copyTable[r1][c1] = current1; copyTable[r2][c2] = current2; } } private int calculateScore2() { int score = 0; for (int r = 0; r < 6; r++) { final int partScoreRow = partScoreRow2(counts_row, r); part_score_row[r] = partScoreRow; score += partScoreRow; } for (int c = 0; c < 6; c++) { final int partScoreColumn = partScoreColumn2(counts_column, c); part_score_column[c] = partScoreColumn; score += partScoreColumn; } return score; } private int partScoreColumn2(int[][] counts_column, int c) { Arrays.fill(counts_column[c], 0); int mask = (1 << 6) - 1; for (int r = 0; r < 6; r++) { int index = copyTable[r][c]; int mask2 = 0; for (int i = 0; i < 6; i++) { counts_column[c][dice[index][i]]++; mask2 |= (1 << dice[index][i]); } mask &= mask2; } int part_score = 0; for (int i = 0; i < 6; i++) { if ((mask & (1 << i)) == 0) { continue; } part_score += 3; part_score += counts_column[c][i] - 6; } return part_score; } private int partScoreRow2(int[][] counts_row, int r) { Arrays.fill(counts_row[r], 0); int mask = (1 << 6) - 1; for (int c = 0; c < 6; c++) { int index = copyTable[r][c]; int mask2 = 0; for (int i = 0; i < 6; i++) { counts_row[r][dice[index][i]]++; mask2 |= (1 << dice[index][i]); } mask &= mask2; } int part_score = 0; for (int i = 0; i < 6; i++) { if ((mask & (1 << i)) == 0) { continue; } part_score += 3; part_score += counts_row[r][i] - 6; } return part_score; } private int calculateScore(int[][] table) { int score = 0; for (int r = 0; r < 6; r++) { score += partScoreRow(table, r); } for (int c = 0; c < 6; c++) { score += partScoreColumn(table, c); } return score; } private int partScoreColumn(int[][] table, int c) { Arrays.fill(counts, 0); int mask = (1 << 6) - 1; int count_r = 0; for (int r = 0; r < 6; r++) { int index = table[r][c]; if (index < 0) { continue; } count_r++; int mask2 = 0; for (int i = 0; i < 6; i++) { counts[dice[index][i]]++; mask2 |= (1 << dice[index][i]); } mask &= mask2; } int part_score = 0; for (int i = 0; i < 6; i++) { if ((mask & (1 << i)) == 0) { continue; } if (counts[i] == 0) { continue; } part_score += 3; part_score += counts[i] - count_r; } return part_score; } private int partScoreRow(int[][] table, int r) { Arrays.fill(counts, 0); int mask = (1 << 6) - 1; int count_c = 0; for (int c = 0; c < 6; c++) { int index = table[r][c]; if (index < 0) { continue; } count_c++; int mask2 = 0; for (int i = 0; i < 6; i++) { counts[dice[index][i]]++; mask2 |= (1 << dice[index][i]); } mask &= mask2; } int part_score = 0; for (int i = 0; i < 6; i++) { if ((mask & (1 << i)) == 0) { continue; } if (counts[i] == 0) { continue; } part_score += 3; part_score += counts[i] - count_c; } return part_score; } } class SAState { public static final boolean useTime = !true; public double startTime; public double endTime; public double time; public double startTemperature; public double endTemperature; public double inverseTemperature; public double lastAcceptTemperature; public double startRange; public double endRange; public double range; public int numIterations; public int validIterations; public int acceptIterations; private double[] log = new double[32768]; public SAState() { for (int i = 0; i < log.length; i++) { log[i] = Math.log((i + 0.5) / log.length); } } public void init() { numIterations = 0; validIterations = 0; acceptIterations = 0; startTime = useTime ? Constants.watch.getSecond() : numIterations; update(); lastAcceptTemperature = inverseTemperature; } public void update() { updateTime(); updateTemperature(); } public boolean useExp = !true; public void updateTemperature() { if (useExp) { double time0to1 = elapsedPercentage(startTime, endTime, time); double startY = startTemperature; double endY = endTemperature; double startX = Math.log(startY); double endX = Math.log(endY); double xStartToEnd = interpolate(startX, endX, time0to1); double temperature = Math.exp(xStartToEnd); inverseTemperature = 1.0 / temperature; } else { double time0to1 = elapsedPercentage(startTime, endTime, time); double startY = startTemperature; double endY = endTemperature; double temperature = interpolate(startY, endY, time0to1); inverseTemperature = 1.0 / temperature; } } private double elapsedPercentage(double min, double max, double v) { return (v - min) / (max - min); } private double interpolate(double v0, double v1, double d0to1) { return v0 + (v1 - v0) * d0to1; } public void updateRange() { range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0); } public void updateTime() { time = useTime ? Constants.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; } double d = deltaScore * inverseTemperature; if (d < -10) { return false; } if (log[Constants.RNG.nextInt() & 32767] < d) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } public boolean acceptS(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } double d = -deltaScore * inverseTemperature; if (d < -10) { return false; } if (log[Constants.RNG.nextInt() & 32767] < d) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } } final class Utils { private Utils() { } public static final void debug(Object... o) { System.err.println(toString(o)); System.err.flush(); } public static final String toString(Object... o) { return Arrays.deepToString(o); } public static boolean isValid(int v, int min, int minUpper) { return v >= min && v < minUpper; } } 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)); } } } interface Constants { Watch watch = new Watch(); PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime()); } final class PCG_XSH_RR { private long state = 5342; public PCG_XSH_RR(final long state) { this.state = state; } public int nextInt() { final long oldstate = state; state = oldstate * 6364136223846793005L + 521L; final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27); final int rotation = (int) (oldstate >>> 59); return (xorshift >>> rotation) | (xorshift << (-rotation & 31)); } public int nextInt(int n) { return (int) (n * nextDouble()); } public double nextDouble() { return (nextInt() >>> 1) * 4.6566128730773926E-10; } }