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 void reverseInPlace(final ArrayList 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; } }