結果
| 問題 | No.5010 Better Mo's Algorithm is Needed!! (Unweighted) |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2022-12-17 15:53:22 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,523 bytes |
| コンパイル時間 | 3,608 ms |
| 実行使用メモリ | 59,364 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-12-17 15:53:44 |
| 合計ジャッジ時間 | 21,017 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
| testcase_100 | -- | - |
| testcase_101 | -- | - |
| testcase_102 | -- | - |
| testcase_103 | -- | - |
| testcase_104 | -- | - |
| testcase_105 | -- | - |
| testcase_106 | -- | - |
| testcase_107 | -- | - |
| testcase_108 | -- | - |
| testcase_109 | -- | - |
| testcase_110 | -- | - |
| testcase_111 | -- | - |
| testcase_112 | -- | - |
| testcase_113 | -- | - |
| testcase_114 | -- | - |
| testcase_115 | -- | - |
| testcase_116 | -- | - |
| testcase_117 | -- | - |
| testcase_118 | -- | - |
| testcase_119 | -- | - |
ソースコード
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.stream.IntStream;
public class Main {
final int e = 750;
final int e2 = e / 5;
private int N;
private int Q;
private int WT;
private int ST;
private int[] W;
private int[] L;
private int[] R;
private int[] P;
private long[] cumsumW;
private long score;
private long bestScore;
private SAState sa = new SAState();
public static void main(String[] args) {
new Main().run();
}
private void run() {
read();
init();
greedy();
multiSA();
write();
}
private void read() {
try (Scanner in = new Scanner(System.in)) {
N = in.nextInt();
Q = in.nextInt();
WT = in.nextInt();
ST = in.nextInt();
W = IntStream.range(0, N).map(i -> in.nextInt()).toArray();
L = new int[Q];
R = new int[Q];
IntStream.range(0, Q).forEach(i -> {
L[i] = in.nextInt() - 1;
R[i] = in.nextInt() - 1;
});
} catch (Exception e) {
e.printStackTrace();
}
}
private void init() {
cumsumW = new long[N + 1];
IntStream.range(0, N).forEach(i -> cumsumW[i + 1] = cumsumW[i] + W[i]);
}
private void greedy() {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
list.add(i);
}
Collections.sort(list, (o1, o2) -> {
{
if (L[o1] / e < L[o2] / e) {
return -1;
}
if (L[o1] / e > L[o2] / e) {
return 1;
}
int coef = (L[o1] / e) % 2 == 0 ? 1 : -1;
if (R[o1] / e < R[o2] / e) {
return coef * -1;
}
if (R[o1] / e > R[o2] / e) {
return coef * 1;
}
}
{
if (L[o1] / e2 < L[o2] / e2) {
return -1;
}
if (L[o1] / e2 > L[o2] / e2) {
return 1;
}
int coef = (L[o1] / e2) % 2 == 0 ? 1 : -1;
if (R[o1] / e2 < R[o2] / e2) {
return coef * -1;
}
if (R[o1] / e2 > R[o2] / e2) {
return coef * 1;
}
}
return 0;
});
P = new int[N];
for (int i = 0; i < P.length; i++) {
P[i] = list.get(i).intValue();
}
score = calculateScore(P, N);
Utils.debug("greedy", "score", score);
}
private void multiSA() {
int numRestart = 1;
double startTime = Constants.watch.getSecond();
double endTime = 5 - 0.25;
double remainTime = endTime - startTime;
double startStartTemperature = 1e4;
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() {
double second = Constants.watch.getSecond();
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.time > second) {
second += 1;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%6d", score), String.format("%6d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
if (sa.isTLE()) {
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%6d", score), String.format("%6d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}
}
mutate();
}
}
private void mutate() {
reverse();
}
private void reverse() {
int l = Constants.RNG.nextInt(N);
final int d = 10;
int r = l - d + Constants.RNG.nextInt(2 * d);
while (r == l || r < 0 || r >= N) {
r = l - d + Constants.RNG.nextInt(2 * d);
}
if (l > r) {
int swap = l;
l = r;
r = swap;
}
long before = calculatePartScore(P, l) + (r + 1 >= N ? 0 : calculatePartScore(P, r + 1));
{
int swap = P[l];
P[l] = P[r];
P[r] = swap;
}
long after = calculatePartScore(P, l) + (r + 1 >= N ? 0 : calculatePartScore(P, r + 1));
{
int swap = P[l];
P[l] = P[r];
P[r] = swap;
}
long deltaScore = after - before;
if (sa.accept(deltaScore)) {
score += deltaScore;
for (; l < r; l++, r--) {
int swap = P[l];
P[l] = P[r];
P[r] = swap;
}
} else {
}
}
private void write() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < P.length; i++) {
if (i > 0) {
sb.append(" ");
}
sb.append(1 + P[i]);
}
System.out.println(sb.toString());
System.out.flush();
}
private long calculateScore(int[] P, int N) {
long T = 0;
for (int pi = 0; pi < P.length; pi++) {
T += calculatePartScore(P, pi);
}
return T;
}
private long calculatePartScore(int[] P, int pi) {
if (pi - 1 < 0) {
return cumsumW[1 + R[P[0]]] - cumsumW[L[P[0]]];
} else {
int minL = Math.min(L[P[pi - 1]], L[P[pi]]);
int maxL = Math.max(L[P[pi - 1]], L[P[pi]]);
int minR = Math.min(R[P[pi - 1]], R[P[pi]]);
int maxR = Math.max(R[P[pi - 1]], R[P[pi]]);
return cumsumW[maxL] - cumsumW[minL] + cumsumW[1 + maxR] - cumsumW[1 + minR];
}
}
}
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);
}
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));
}
}
}
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();
updateRange();
}
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() {
double time0to1 = elapsedPercentage(startTime, endTime, time);
double startY = startRange;
double endY = endRange;
range = interpolate(startY, endY, time0to1);
}
public void updateTime() {
time = useTime ? Constants.watch.getSecond() : numIterations;
}
public boolean isTLE() {
return time >= endTime;
}
public boolean accept(double deltaScore) {
return acceptS(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 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;
}
}
interface Constants {
Watch watch = new Watch();
PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime());
}