結果
| 問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2022-10-15 00:57:04 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 803 ms / 2,000 ms |
| コード長 | 18,321 bytes |
| コンパイル時間 | 5,501 ms |
| 実行使用メモリ | 46,012 KB |
| スコア | 864,461,088,373,148 |
| 最終ジャッジ日時 | 2022-10-15 00:58:23 |
| 合計ジャッジ時間 | 47,809 ms |
|
ジャッジサーバーID （参考情報） |
judge8 / judge9 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.util.HashMap;import java.util.Random;public class Main {public static void main(String[] args) {new Main();}public Main() {FastScanner fs = new FastScanner();java.io.PrintWriter out = new java.io.PrintWriter(System.out);solve(fs, out);out.flush();}public void solve(FastScanner fs, java.io.PrintWriter out) {int N = fs.nextInt();Calc calc = new Calc(fs);FastRandom rnd = new FastRandom();Pendulum left = new Pendulum(1, 1, 1, calc), right = new Pendulum(1, 1, 1, calc);long time = System.currentTimeMillis();for (int B = 1;B <= 150;++ B) {for (int M = 1;M <= B;++ M) {for (int E = 1;E <= Math.min(100, B - M + 1);++ E) {Pendulum pen = new Pendulum(B, M, E, calc);if (left.score < pen.score) left = pen;if (right.score > pen.score) right = pen;}}}// while(System.currentTimeMillis() - time < 1700) {// int B = (rnd.nextInt() & 0xFFF) + 1;// int M = rnd.nextInt(B) + 1;// int E = rnd.nextInt(B - M + 1) + 1;// Pendulum pen = new Pendulum(B, M, E, calc);// if (left.score < pen.score) left = pen;// if (right.score > pen.score) right = pen;// }for (int i = 0;i < N / 2;++ i) {out.println(left.B + " " + left.M + " " + left.E);}for (int i = 0;i < N / 2;++ i) {out.println(right.B + " " + right.M + " " + right.E);}System.err.println(System.currentTimeMillis() - time + " ms");}class Pendulum{final int B, M, E;double score;Pendulum(int B, int M, int E, Calc calc) {this.B = B;this.M = M;this.E = E;score = calc.left(B, M, E);}}static class Calc {int K;int[] T, U;boolean firstT;Calc(FastScanner fs) {K = fs.nextInt();T = new int[K];for (int i = 0; i < K; ++i) T[i] = fs.nextInt();U = new int[K];for (int i = 0; i < K; ++i) U[i] = fs.nextInt();firstT = T[0] < U[0];}double left(int B, final int M, final int E) {int firstB = B;int last = 0;int point = 0;boolean right = true;long confrontation = 0, cooperation = 0;if (firstT) {for (int i = 0; i < K; ++i) {int next = T[i];int move = next - last;while (B != M) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;}B = Math.max(M, B - E);right = !right;}if (B == M) {move %= 4 * M;while (move != 0) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;move -= bound;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;move -= bound;}right = !right;}}confrontation += point;last = next;next = U[i];move = next - last;while (B != M) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;}B = Math.max(M, B - E);right = !right;}if (B == M) {move %= 4 * M;while (move != 0) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;move -= bound;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;move -= bound;}right = !right;}}cooperation += Math.abs(point);}} else {for (int i = 0; i < K; ++i) {int next = U[i];int move = next - last;while (B != M) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;}B = Math.max(M, B - E);right = !right;}if (B == M) {move %= 4 * M;while (move != 0) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;move -= bound;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;move -= bound;}right = !right;}}cooperation += Math.abs(point);last = next;next = T[i];move = next - last;while (B != M) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;}B = Math.max(M, B - E);right = !right;}if (B == M) {move %= 4 * M;while (move != 0) {if (right) {int bound = B - point;if (move < bound) {point += move;break;}point = B;move -= bound;} else {int bound = point - B;if (move < bound) {point -= move;break;}point = -B;move -= bound;}right = !right;}}confrontation += point;}}return score(firstB, confrontation, cooperation);}double right(int B, int M, int E) {return -left(B, M, E);}double score(int B, long confrontation, long cooperation) {return confrontation / Math.sqrt(60.0 * cooperation / K + 1) / B;}}public static final class FastRandom extends Random {private static final long serialVersionUID = 7221542624522369695L;private long rand;private static final float FLOAT_INV = 1f / (1 << 24);private static final double DOUBLE_INV = 1. / (1L << 53);public FastRandom() {this(new Random().nextLong());}public FastRandom(long seed) {rand = seed;}@Overridepublic void setSeed(long seed) { rand = seed; }@Overrideprotected int next(int bits) {return (int) nextLong() & (1 << bits) - 1;}@Overridepublic int nextInt() {rand = rand ^ rand << 7;rand = rand ^ rand >>> 9;return (int) (rand & Integer.MAX_VALUE);}@Overridepublic int nextInt(int bounds) {int maxUse = Integer.MAX_VALUE / bounds * bounds;while (true) {int val = nextInt();if (val < maxUse) return val % bounds;}}/*** startInclusive以上endExclusive未満の値をcount個、重複無しで生成します。* @param startInclusive 下限* @param endExclusive 上限* @param count 個数* @return startInclusive以上endExclusive未満の値が重複無しでcount個入った配列*/public int[] nextInts(int startInclusive, int endExclusive, int count) {if (endExclusive - startInclusive < count) throw new IllegalArgumentException();int len = endExclusive - startInclusive;int[] result = new int[count];HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < count; ++i) {int target = nextInt(len - i);int l = map.getOrDefault(i, i);int r = map.getOrDefault(target, target);map.put(target, l);result[i] = r + startInclusive;}return result;}public int nextRange(int startInclusive, int endExclusive) {if (startInclusive >= endExclusive) throw new IllegalArgumentException();return nextInt(endExclusive - startInclusive) + startInclusive;}@Overridepublic long nextLong() {rand = rand ^ rand << 7;rand = rand ^ rand >>> 9;return rand & Long.MAX_VALUE;}public long nextLong(long bounds) {long maxUse = Long.MAX_VALUE / bounds * bounds;while (true) {long val = nextLong();if (val < maxUse) return val % bounds;}}public long nextRange(long startInclusive, long endExclusive) {if (startInclusive >= endExclusive) throw new IllegalArgumentException();return nextLong(endExclusive - startInclusive) + startInclusive;}/*** startInclusive以上endExclusive未満の値をcount個、重複無しで生成します。* @param startInclusive 下限* @param endExclusive 上限* @param count 個数* @return startInclusive以上endExclusive未満の値が重複無しでcount個入った配列*/public long[] nextLongs(long startInclusive, long endExclusive, int count) {if (endExclusive - startInclusive < count) throw new IllegalArgumentException();long len = endExclusive - startInclusive;long[] result = new long[count];HashMap<Long, Long> map = new HashMap<>();for (int i = 0; i < count; ++i) {long target = nextLong(len - i);long l = map.getOrDefault((long) i, (long) i);long r = map.getOrDefault(target, target);map.put(target, l);result[i] = r + startInclusive;}return result;}@Overridepublic boolean nextBoolean() {rand = rand ^ rand << 7;rand = rand ^ rand >>> 9;return (rand & 1) != 0;}@Overridepublic float nextFloat() {rand = rand ^ rand << 7;rand = rand ^ rand >>> 9;return (int) (rand & 0x00FFFFFF) * FLOAT_INV;}@Overridepublic double nextDouble() {rand = rand ^ rand << 7;rand = rand ^ rand >>> 9;return (rand & 0x001FFFFFFFFFFFFFL) * DOUBLE_INV;}public double nextDouble(double startInclusive, double endExclusive) {return startInclusive + nextDouble() * (endExclusive - startInclusive);}}final int MOD = 998_244_353;int plus(int n, int m) {int sum = n + m;if (sum >= MOD) sum -= MOD;return sum;}int minus(int n, int m) {int sum = n - m;if (sum < 0) sum += MOD;return sum;}int times(int n, int m) {return (int) ((long) n * m % MOD);}int divide(int n, int m) {return times(n, IntMath.pow(m, MOD - 2, MOD));}int[] fact, invf;void calc(int len) {len += 2;fact = new int[len];invf = new int[len];fact[0] = fact[1] = invf[0] = invf[1] = 1;for (int i = 2; i < fact.length; ++i) fact[i] = times(fact[i - 1], i);invf[len - 1] = divide(1, fact[len - 1]);for (int i = len - 1; i > 1; --i) invf[i - 1] = times(i, invf[i]);}int comb(int n, int m) {if (n < m) return 0;return times(fact[n], times(invf[n - m], invf[m]));}}class FastScanner {private final java.io.InputStream in = System.in;private final byte[] buffer = new byte[8192];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) return true;ptr = 0;try {buflen = in.read(buffer);} catch (java.io.IOException e) {e.printStackTrace();}return buflen > 0;}private byte readByte() {return hasNextByte() ? buffer[ptr++] : -1;}private static boolean isPrintableChar(byte c) {return 32 < c || c < 0;}private static boolean isNumber(int c) {return '0' <= c && c <= '9';}public boolean hasNext() {while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;return hasNextByte();}public String next() {if (!hasNext()) throw new java.util.NoSuchElementException();StringBuilder sb = new StringBuilder();byte b;while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);return sb.toString();}public final char nextChar() {if (!hasNext()) throw new java.util.NoSuchElementException();return (char) readByte();}public final long nextLong() {if (!hasNext()) throw new java.util.NoSuchElementException();long n = 0;try {byte b = readByte();if (b == '-') {while (isNumber(b = readByte())) n = n * 10 + '0' - b;return n;} else if (!isNumber(b)) throw new NumberFormatException();do n = n * 10 + b - '0'; while (isNumber(b = readByte()));} catch (java.util.NoSuchElementException e) {}return n;}public final int nextInt() {if (!hasNext()) throw new java.util.NoSuchElementException();int n = 0;try {byte b = readByte();if (b == '-') {while (isNumber(b = readByte())) n = n * 10 + '0' - b;return n;} else if (!isNumber(b)) throw new NumberFormatException();do n = n * 10 + b - '0'; while (isNumber(b = readByte()));} catch (java.util.NoSuchElementException e) {}return n;}public double nextDouble() {return Double.parseDouble(next());}}class Arrays {public static void sort(final int[] array) {sort(array, 0, array.length);}public static void sort(final int[] array, int fromIndex, int toIndex) {if (toIndex - fromIndex <= 512) {java.util.Arrays.sort(array, fromIndex, toIndex);return;}sort(array, fromIndex, toIndex, 0, new int[array.length]);}private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {if (to - from <= 512) {java.util.Arrays.sort(a, from, to);return;}final int BUCKET_SIZE = 256;final int INT_RECURSION = 4;final int MASK = 0xff;final int shift = l << 3;final int[] cnt = new int[BUCKET_SIZE + 1];final int[] put = new int[BUCKET_SIZE];for (int i = from; i < to; i++) ++cnt[(a[i] >>> shift & MASK) + 1];for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];for (int i = from; i < to; i++) {int bi = a[i] >>> shift & MASK;bucket[cnt[bi] + put[bi]++] = a[i];}for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {int begin = cnt[i];int len = cnt[i + 1] - begin;System.arraycopy(bucket, begin, a, idx, len);idx += len;}final int nxtL = l + 1;if (nxtL < INT_RECURSION) {sort(a, from, to, nxtL, bucket);if (l == 0) {int lft, rgt;lft = from - 1;rgt = to;while (rgt - lft > 1) {int mid = lft + rgt >> 1;if (a[mid] < 0) lft = mid;else rgt = mid;}reverse(a, from, rgt);reverse(a, rgt, to);}}}public static void sort(final long[] array) {sort(array, 0, array.length);}public static void sort(final long[] array, int fromIndex, int toIndex) {if (toIndex - fromIndex <= 512) {java.util.Arrays.sort(array, fromIndex, toIndex);return;}sort(array, fromIndex, toIndex, 0, new long[array.length]);}private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) {final int BUCKET_SIZE = 256;final int LONG_RECURSION = 8;final int MASK = 0xff;final int shift = l << 3;final int[] cnt = new int[BUCKET_SIZE + 1];final int[] put = new int[BUCKET_SIZE];for (int i = from; i < to; i++) ++cnt[(int) ((a[i] >>> shift & MASK) + 1)];for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];for (int i = from; i < to; i++) {int bi = (int) (a[i] >>> shift & MASK);bucket[cnt[bi] + put[bi]++] = a[i];}for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {int begin = cnt[i];int len = cnt[i + 1] - begin;System.arraycopy(bucket, begin, a, idx, len);idx += len;}final int nxtL = l + 1;if (nxtL < LONG_RECURSION) {sort(a, from, to, nxtL, bucket);if (l == 0) {int lft, rgt;lft = from - 1;rgt = to;while (rgt - lft > 1) {int mid = lft + rgt >> 1;if (a[mid] < 0) lft = mid;else rgt = mid;}reverse(a, from, rgt);reverse(a, rgt, to);}}}public static void reverse(int[] array) {reverse(array, 0, array.length);}public static void reverse(int[] array, int fromIndex, int toIndex) {for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {int swap = array[fromIndex];array[fromIndex] = array[toIndex];array[toIndex] = swap;}}public static void reverse(long[] array) {reverse(array, 0, array.length);}public static void reverse(long[] array, int fromIndex, int toIndex) {for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {long swap = array[fromIndex];array[fromIndex] = array[toIndex];array[toIndex] = swap;}}public static void shuffle(int[] array) {java.util.Random rnd = new java.util.Random();for (int i = 0; i < array.length; ++i) {int j = rnd.nextInt(array.length - i) + i;int swap = array[i];array[i] = array[j];array[j] = swap;}}public static void shuffle(long[] array) {java.util.Random rnd = new java.util.Random();for (int i = 0; i < array.length; ++i) {int j = rnd.nextInt(array.length - i) + i;long swap = array[i];array[i] = array[j];array[j] = swap;}}}class IntMath {public static int gcd(int a, int b) {while (a != 0) if ((b %= a) != 0) a %= b;else return a;return b;}public static int gcd(int... array) {int ret = array[0];for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);return ret;}public static long gcd(long a, long b) {while (a != 0) if ((b %= a) != 0) a %= b;else return a;return b;}public static long gcd(long... array) {long ret = array[0];for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);return ret;}public static long lcm(long a, long b) {return a / gcd(a, b) * b;}public static int pow(int a, int b) {int ans = 1;for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;return ans;}public static long pow(long a, long b) {long ans = 1;for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;return ans;}public static int pow(int a, long b, int mod) {if (b < 0) b = b % (mod - 1) + mod - 1;long ans = 1;for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod;return (int) ans;}public static int pow(long a, long b, int mod) {return pow((int) (a % mod), b, mod);}public static int floorsqrt(long n) {return (int) Math.sqrt(n + 0.1);}public static int ceilsqrt(long n) {return n <= 1 ? (int) n : (int) Math.sqrt(n - 0.1) + 1;}}