#136248 (Java21) No.456 Millions of Submits!

提出ソース

結果

問題	No.456 Millions of Submits!
ユーザー	37zigen
提出日時	2016-12-08 01:22:07
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	6,110 bytes
コンパイル時間	3,608 ms
コンパイル使用メモリ	81,184 KB
実行使用メモリ	117,076 KB
最終ジャッジ日時	2023-09-05 10:10:25
合計ジャッジ時間	7,390 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	111 ms 39,260 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	RE	-
testcase_04	WA	-
testcase_05	RE	-
testcase_06	WA	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package yukicoder;

import java.util.*;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

class Q456 {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";

	static void solver() {
		int m = ni();
		ArrayList<Double>[][] query = new ArrayList[11][11];
		ArrayList<Double>[][] ans = new ArrayList[11][11];
		for (int i = 0; i < 11; ++i) {
			for (int j = 0; j < 11; ++j) {
				query[i][j] = new ArrayList<>();
				ans[i][j] = new ArrayList<>();
			}
		}
		int[] id = new int[m];
		int[] a = new int[m];
		int[] b = new int[m];
		double[] t = new double[m];
		for (int i = 0; i < m; ++i) {
			a[i] = ni();
			b[i] = ni();
			t[i] = nd();
			id[i] = query[a[i]][b[i]].size();
			query[a[i]][b[i]].add(t[i]);
		}
		for (int aValue = 0; aValue <= 10; ++aValue) {
			for (int bValue = 0; bValue <= 10; ++bValue) {
				if (query[aValue][bValue].size() == 0)
					continue;
				if (aValue < 2 || bValue < 2) {
					Tree tree = new Tree(aValue, bValue);
					for (double v : query[aValue][bValue]) {
						ans[aValue][bValue].add(tree.search(v));
					}
				} else {
					double curN = 20;
					for (double v : query[aValue][bValue]) {
						for (int i = 0; i < 30; ++i) {
							double y = calc(aValue, bValue, curN) - v;
							double yDiff = aValue * pow(curN, aValue - 1) * pow(Math.log1p(curN - 1), bValue);
							yDiff += bValue * pow(curN, aValue - 1) * pow(Math.log1p(curN - 1), bValue - 1);
							curN = curN - y / yDiff;
						}
						ans[aValue][bValue].add(curN);
					}
				}
			}
		}
		for (int i = 0; i < m; ++i) {
			out.printf("%.12f\n", ans[a[i]][b[i]].get(id[i]));
		}
	}

	static class Tree {
		static int gen = 0;
		static int a;
		static int b;
		Node root;

		public Tree(int a, int b) {
			this.a = a;
			this.b = b;
			if (b != 0) {
				root = new Node(1, 20, calc(a, b, 1), calc(a, b, 20), ++gen, 0);
			} else {
				root = new Node(0, 20, calc(a, b, 0), calc(a, b, 20), ++gen, 0);
			}
		}

		double search(double v) {
			Node cur = root;
			out: while (cur.depth < 40) {
				if (cur.p == 0) {
					cur.genChild();
				}
				for (Node c : cur.child) {
					if (c.lv <= v && v <= c.rv) {
						cur = c;
						continue out;
					}
				}
				throw new AssertionError();
			}
			return (cur.l + cur.r) / 2;
		}

		static class Node {
			int id;
			int p = 0;
			double l;
			double r;
			double lv;
			double rv;
			int depth;
			Node[] child = new Node[2];

			public Node(double l, double r, double lv, double rv, int id, int depth) {
				this.id = id;
				this.l = l;
				this.r = r;
				this.lv = lv;
				this.rv = rv;
				this.depth = depth;
			}

			void genChild() {
				double mid = calc(a, b, (l + r) / 2);
				child[p++] = new Node(l, (l + r) / 2, lv, mid, ++gen, this.depth + 1);
				child[p++] = new Node((l + r) / 2, r, mid, rv, ++gen, this.depth + 1);
			}
		}
	}

	static double calc(int a, int b, double n) {
		return pow(n, a) * pow(Math.log1p(n - 1), b);
	}

	static double pow(double a, int n) {
		double ret = 1;
		for (; n > 0; n >>= 1, a *= a) {
			if (n % 2 == 1) {
				ret *= a;
			}
		}
		return ret;
	}

	void run() throws Exception {
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solver();
		out.flush();
		if (!INPUT.isEmpty())
			tr(System.currentTimeMillis() - s + "ms");
		// Thread t = new Thread(null, null, "~",
		// Runtime.getRuntime().maxMemory()){
		// @Override
		// public void run() {
		// long s = System.currentTimeMillis();
		// solve();
		// out.flush();
		// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
		// }
		// };
		// t.start();
		// t.join();
	}

	public static void main(String[] args) throws Exception {
		new Q456().run();
	}

	private static byte[] inbuf = new byte[1024];
	public static int lenbuf = 0;
	public static int ptrbuf = 0;

	private static int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private static boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private static int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private static double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private static String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for (int i = 0; i < n; i++)
			map[i] = na(m);
		return map;
	}

	private static int ni() {
		return (int) nl();
	}

	private static long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private static void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
}