結果
| 問題 | No.456 Millions of Submits! |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-12-07 23:59:16 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,638 bytes |
| コンパイル時間 | 2,228 ms |
| コンパイル使用メモリ | 83,692 KB |
| 実行使用メモリ | 120,548 KB |
| 最終ジャッジ日時 | 2024-06-23 04:31:40 |
| 合計ジャッジ時間 | 5,408 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 47 ms
37,268 KB |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
ソースコード
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) {
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) {
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 - 0.001, 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;
}
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));
}
}