結果

問題 No.456 Millions of Submits!
ユーザー Min_25Min_25
提出日時 2016-12-08 04:15:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,847 ms / 4,500 ms
コード長 2,695 bytes
コンパイル時間 1,362 ms
コンパイル使用メモリ 95,376 KB
実行使用メモリ 4,448 KB
最終ジャッジ日時 2023-09-05 12:06:31
合計ジャッジ時間 8,228 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
4,376 KB
testcase_01 AC 9 ms
4,380 KB
testcase_02 AC 9 ms
4,376 KB
testcase_03 AC 9 ms
4,380 KB
testcase_04 AC 9 ms
4,376 KB
testcase_05 AC 10 ms
4,376 KB
testcase_06 AC 10 ms
4,380 KB
testcase_07 AC 13 ms
4,448 KB
testcase_08 AC 13 ms
4,440 KB
testcase_09 AC 48 ms
4,376 KB
testcase_10 AC 48 ms
4,380 KB
testcase_11 AC 392 ms
4,380 KB
testcase_12 AC 3,847 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>

#include <tuple>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i8 = signed char;
using i16 = signed short;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

int get_int() {
  int c, n;
  while ((c = getchar()) < '0');
  n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + (c - '0');
  return n;
}

using real_t = f80;

real_t get_double() {
  int c, n;
  while ((c = getchar()) < '0');
  n = c - '0';
  while ((c = getchar()) >= '.') if (c != '.') n = n * 10 + (c - '0');
  return n / real_t(10000.0);
}

real_t f(int a, int b, real_t t) {
  real_t res = pow(t, a);
  if (b > 0) res *= pow(log(t), b);
  return res;
}

static vector< pair<real_t, real_t> > pre[11][11];

real_t calc(int a, int b, real_t t) {
  if (a == 0) {
    assert(b > 0);
    return exp(pow(t, real_t(1) / b));
  } else if (b == 0) {
    assert(a > 0);
    return pow(t, real_t(1) / a);
  } else {
    int ind = upper_bound(pre[a][b].begin(), pre[a][b].end(), 
                make_pair(t, real_t(0))) - pre[a][b].begin() - 1;
    auto x = pre[a][b][ind].second;
    assert(pre[a][b][ind].first <= t && t < pre[a][b][ind + 1].first);
    rep(_, 4) {
      auto log_x = log(x);
      auto x_pow = pow(x, a - 1), logx_pow = pow(log_x, b - 1);
      auto numer = x_pow * logx_pow * x * log_x - t;
      auto denom = x_pow * logx_pow * (a * log_x + b);
      x -= numer / denom;
    }
    return x;
  }
}

void solve() {
  rep(a, 11) rep(b, 11) if (a && b) {
    real_t step = 0.00987654321;
    for (real_t x = 1.0; ; x += step) {
      real_t y = f(a, b, x);
      pre[a][b].emplace_back(y, x);
      if (y > 10.0) break;
    }
  }
  int T; scanf("%d", &T);
  rep(_, T) {
    int a = get_int(), b = get_int();
    real_t t; scanf("%Lf", &t);
    // auto t = get_double();
    auto ans = calc(a, b, t);
    assert(f(a, b, ans + 1e-10L) > t);
    assert(f(a, b, ans - 1e-10L) < t);
    printf("%.12Lf\n", ans);
  }
}

int main() {
  auto beg = clock();
  solve();
  auto end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
}
0