結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:55:56 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,945 ms / 2,000 ms |
コード長 | 12,787 bytes |
コンパイル時間 | 3,282 ms |
実行使用メモリ | 54,360 KB |
スコア | 387,125,189,424,599 |
最終ジャッジ日時 | 2022-10-14 23:57:48 |
合計ジャッジ時間 | 110,324 ms |
ジャッジサーバーID (参考情報) |
judge8 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
import java.util.ArrayList;import java.util.Arrays;import java.util.Calendar;import java.util.Scanner;import java.util.TimeZone;import java.util.stream.IntStream;public class Main {final int maxB = 1000000;private int N;private int K;private int[] T;private int[] U;private int[] B;private int[] M;private int[] E;private double score = (int) -1e18;private double bestScore = -1e18;private SAState sa = new SAState();public static void main(String[] args) throws Exception {// Utils.debug(CalendarUtils.toStringTimeLeft(new Calendar.Builder().setTimeZone(TimeZone.getTimeZone("GMT+9:00")).setInstant(Calendar.getInstance().getTime()).build(), Constants.endTime));new Main().run();}private void run() {read();solve();write();}private void read() {try (final Scanner in = new Scanner(System.in)) {N = in.nextInt();Constants.watch.init();K = in.nextInt();T = IntStream.range(0, K).map(i -> in.nextInt()).toArray();U = IntStream.range(0, K).map(i -> in.nextInt()).toArray();} catch (Exception e) {e.printStackTrace();}}private void solve() {B = new int[N];M = new int[N];E = new int[N];for (int i = 0; i < N; i++) {B[i] = 1 + Constants.RNG.nextInt(maxB);M[i] = B[i];E[i] = 1;}score = calculateScore();multiSA();// Utils.debug("time", Constants.watch.getSecondString());}private void saveBest() {if (score > bestScore) {bestScore = score;}}private void restoreBest() {}private void multiSA() {int numRestart = 1;double startTime = Constants.watch.getSecond();double endTime = 1.75;double remainTime = endTime - startTime;double startStartTemperature = 1e1;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();}// Utils.debug("multiSA", "score", score, "time", Constants.watch.getSecondString());}private void SA() {// final double deltaSecond = (sa.endTime - sa.startTime) * 0.999 / 10;// double thresholdSecond = sa.startTime + deltaSecond;sa.init();for (;; ++sa.numIterations) {if ((sa.numIterations & ((1 << 5) - 1)) == 0) {sa.update();// if (sa.time > thresholdSecond) {// thresholdSecond += deltaSecond;// Utils.debug(sa.numIterations, String.format("%6.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%6.2f%%",100.0 * sa.acceptIterations / sa.validIterations), String.format("%5.0f", score), String.format("%5.0f", bestScore), String.format("%8.6f", 1.0 /sa.inverseTemperature), String.format("%8.6f", 1.0 / sa.lastAcceptTemperature), sa.time);// }if (sa.isTLE()) {break;}}mutate();}}private void mutate() {change();}private void change() {int i = sa.numIterations % N;int current = B[i];B[i] = 1 + Constants.RNG.nextInt(maxB);double deltaScore = calculateScore() - score;if (sa.accept(deltaScore)) {score += deltaScore;M[i] = B[i];saveBest();} else {B[i] = current;}}private double calculateScore() {int[] x = new int[N];double scoreT = 0;for (int k = 0; k < K; k++) {for (int n = 0; n < N; n++) {x[n] = T[k] % (4 * B[n]);if (x[n] <= B[n]) {x[n] = 0 + (x[n] - 0);} else if (x[n] <= 2 * B[n]) {x[n] = (B[n] - 1) - (x[n] - B[n]);} else if (x[n] <= 3 * B[n]) {x[n] = 0 - (x[n] - 2 * B[n]);} else if (x[n] < 4 * B[n]) {x[n] = -(B[n] - 1) + (x[n] - 3 * B[n]);}}double sum = 0;for (int i = 0; i < x.length; i++) {for (int j = i + 1; j < x.length; j++) {sum += Math.abs(x[i] - x[j]) / (double) (B[i] + B[j]);}}scoreT += 2e7 / (N * (N - 1)) * sum;}double scoreU = 0;for (int k = 0; k < K; k++) {for (int n = 0; n < N; n++) {x[n] = U[k] % (4 * B[n]);if (x[n] <= B[n]) {x[n] = 0 + (x[n] - 0);} else if (x[n] <= 2 * B[n]) {x[n] = (B[n] - 1) - (x[n] - B[n]);} else if (x[n] <= 3 * B[n]) {x[n] = 0 - (x[n] - 2 * B[n]);} else if (x[n] < 4 * B[n]) {x[n] = -(B[n] - 1) + (x[n] - 3 * B[n]);}}double max = 0;for (int i = 0; i < x.length; i++) {for (int j = i + 1; j < x.length; j++) {max += Math.abs(x[i] - x[j]);}}scoreU += 1e7 / Math.sqrt(1 + max / 20.0);}scoreT /= K;scoreU /= K;return scoreU * scoreT * 1e-9;}private void write() {StringBuilder sb = new StringBuilder();for (int i = 0; i < N; i++) {sb.append(B[i]).append(' ');sb.append(M[i]).append(' ');sb.append(E[i]).append('\n');}System.out.print(sb.toString());System.out.flush();}}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;}public static final int manhattanDistance(final int r1, final int c1, final int r2, final int c2) {final int deltaR = r2 - r1;final int deltaC = c2 - c1;return Math.abs(deltaR) + Math.abs(deltaC);}public static final <T> void reverseInPlace(final ArrayList<T> list) {for (int l = 0, r = list.size() - 1; l < r; l++, r--) {list.set(r, list.set(l, list.get(r)));}}}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 {Calendar startTime = new Calendar.Builder().setTimeZone(TimeZone.getTimeZone("GMT+9:00")).set(Calendar.YEAR, 2022).set(Calendar.MONTH, 8 - 1).set(Calendar.DAY_OF_MONTH, 6).set(Calendar.HOUR_OF_DAY, 1).set(Calendar.MINUTE, 35).set(Calendar.SECOND, 0).build();Calendar endTime = new Calendar.Builder().setTimeZone(TimeZone.getTimeZone("GMT+9:00")).set(Calendar.YEAR, 2022).set(Calendar.MONTH, 8 - 1).set(Calendar.DAY_OF_MONTH, 9).set(Calendar.HOUR_OF_DAY, 1).set(Calendar.MINUTE, 35).set(Calendar.SECOND, 0).build();Watch watch = new Watch();PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime());int[] dr = { -1, 0, 0, 1, };int[] dc = { 0, -1, 1, 0, };}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;}}