#807568 (Java21) No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance

• 問題: No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
• ユーザー: CuriousFairy315
• 提出日時: 2022-10-15 00:57:04
• 言語: Java21 (openjdk 21)
• 結果: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	734 ms; 43,724 KB
testcase_01	AC	737 ms; 43,808 KB
testcase_02	AC	712 ms; 45,752 KB
testcase_03	AC	741 ms; 45,600 KB
testcase_04	AC	731 ms; 45,728 KB
testcase_05	AC	768 ms; 45,792 KB
testcase_06	AC	697 ms; 45,508 KB
testcase_07	AC	730 ms; 43,492 KB
testcase_08	AC	715 ms; 43,584 KB
testcase_09	AC	766 ms; 45,428 KB
testcase_10	AC	752 ms; 43,440 KB
testcase_11	AC	763 ms; 45,524 KB
testcase_12	AC	735 ms; 45,684 KB
testcase_13	AC	657 ms; 46,012 KB
testcase_14	AC	774 ms; 45,568 KB
testcase_15	AC	707 ms; 45,444 KB
testcase_16	AC	803 ms; 45,540 KB
testcase_17	AC	775 ms; 43,632 KB
testcase_18	AC	713 ms; 45,468 KB
testcase_19	AC	736 ms; 43,512 KB
testcase_20	AC	760 ms; 43,796 KB
testcase_21	AC	733 ms; 45,628 KB
testcase_22	AC	725 ms; 44,152 KB
testcase_23	AC	701 ms; 43,432 KB
testcase_24	AC	777 ms; 43,844 KB
testcase_25	AC	728 ms; 43,592 KB
testcase_26	AC	706 ms; 43,728 KB
testcase_27	AC	712 ms; 45,512 KB
testcase_28	AC	716 ms; 45,544 KB
testcase_29	AC	717 ms; 43,636 KB
testcase_30	AC	721 ms; 43,504 KB
testcase_31	AC	783 ms; 43,816 KB
testcase_32	AC	683 ms; 43,584 KB
testcase_33	AC	702 ms; 43,832 KB
testcase_34	AC	713 ms; 43,576 KB
testcase_35	AC	724 ms; 45,724 KB
testcase_36	AC	745 ms; 43,612 KB
testcase_37	AC	711 ms; 45,788 KB
testcase_38	AC	709 ms; 45,632 KB
testcase_39	AC	756 ms; 43,696 KB
testcase_40	AC	716 ms; 43,636 KB
testcase_41	AC	757 ms; 44,112 KB
testcase_42	AC	706 ms; 43,648 KB
testcase_43	AC	749 ms; 43,888 KB
testcase_44	AC	800 ms; 45,572 KB
testcase_45	AC	763 ms; 43,716 KB
testcase_46	AC	739 ms; 43,672 KB
testcase_47	AC	696 ms; 45,588 KB
testcase_48	AC	762 ms; 45,576 KB
testcase_49	AC	720 ms; 43,652 KB

ソースコード

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;
		}

		@Override
		public void setSeed(long seed) { rand = seed; }

		@Override
		protected int next(int bits) {
			return (int) nextLong() & (1 << bits) - 1;
		}

		@Override
		public int nextInt() {
			rand = rand ^ rand << 7;
			rand = rand ^ rand >>> 9;
			return (int) (rand & Integer.MAX_VALUE);
		}

		@Override
		public 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;
		}

		@Override
		public 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;
		}

		@Override
		public boolean nextBoolean() {
			rand = rand ^ rand << 7;
			rand = rand ^ rand >>> 9;
			return (rand & 1) != 0;
		}

		@Override
		public float nextFloat() {
			rand = rand ^ rand << 7;
			rand = rand ^ rand >>> 9;
			return (int) (rand & 0x00FFFFFF) * FLOAT_INV;
		}

		@Override
		public 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;
	}
}