結果

問題 No.456 Millions of Submits!
コンテスト
ユーザー 37zigen
提出日時 2016-12-07 23:49:17
言語 Java
(openjdk 23)
結果
RE  
実行時間 -
コード長 2,663 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,412 ms
コンパイル使用メモリ 80,492 KB
実行使用メモリ 137,420 KB
最終ジャッジ日時 2024-06-23 04:23:33
合計ジャッジ時間 14,200 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 RE * 11 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package yukicoder;

import java.util.*;

public class Q456 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		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] = sc.nextInt();
			b[i] = sc.nextInt();
			t[i] = sc.nextDouble();
			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) {
				Tree tree = new Tree(aValue, bValue);
				for (double v : query[aValue][bValue]) {
					ans[aValue][bValue].add(tree.search(v));
				}
			}
		}
		for (int i = 0; i < m; ++i) {
			System.out.println(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(Math.E, 100, calc(a, b, Math.E), calc(a, b, 100), ++gen, 0);
			} else {
				root = new Node(0, 100, calc(a, b, 0), calc(a, b, 100), ++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) {
			//		System.out.println(v + " " + c.lv + " " + c.rv);
					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.log(n), 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;
	}

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

}
0