#242447 (C++17) No.456 Millions of Submits!

提出ソース

結果

問題	No.456 Millions of Submits!
ユーザー	rsk0315
提出日時	2018-03-09 03:22:53
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,743 ms / 4,500 ms
コード長	13,216 bytes
コンパイル時間	520 ms
コンパイル使用メモリ	64,860 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-15 14:02:22
合計ジャッジ時間	6,651 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	20 ms 5,376 KB
testcase_10	AC	20 ms 5,376 KB
testcase_11	AC	179 ms 5,376 KB
testcase_12	AC	1,743 ms 5,376 KB

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

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:463:5: warning: 'b' may be used uninitialized [-Wmaybe-uninitialized]
  463 |     if (b == 0) {
      |     ^~
main.cpp:459:12: note: 'b' was declared here
  459 |     int a, b;
      |            ^
main.cpp:468:13: warning: 't' may be used uninitialized [-Wmaybe-uninitialized]
  468 |       printf("%.12f\n", exp(pow(t, 1.0/b)));
      |       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:460:12: note: 't' was declared here
  460 |     double t;
      |            ^

ソースコード

raw source code

#include <cstdio>
#include <cstring>
#include <cstdint>
#include <cstdlib>
#include <cstddef>
#include <cinttypes>
#include <cfenv>
#include <cmath>

#include <type_traits>
#include <limits>
#include <algorithm>

namespace FastIn {
  static constexpr size_t BUF_SIZE=1<<17, INT_LEN=24, FLT_LEN=400;
  static char buf[BUF_SIZE|1]={}, *pos=buf, *endbuf=nullptr;
  FILE *fin;

  inline bool rebuffer() {
    // returns true <=> there is at least one unread character
    size_t rest=endbuf-pos;
    if (buf+rest > pos) {
      // buf[:pos] and buf[-pos:] are overlapping, which std::memcpy()
      // causes undefined behavior.
      return true;
    }

    std::memcpy(buf, pos, rest); 
    pos = buf;
    size_t len=std::fread(pos+rest, 1, BUF_SIZE-rest, fin);
    *(endbuf = buf + (rest+len)) = 0;

    return *pos;
  }

  inline bool scan(char &in) {
    if ((in = *pos)) {
      ++pos;
      return true;
    }

    return rebuffer() && (in = *pos++);
  }

  inline bool scan(char *in) {
    if ((*in = *pos) == 0) {
      if (rebuffer() && (*in = *pos) == 0) {
        return false;
      }
    }
    ++in;
    while (true) {
      if ((*in = *pos++) == 0) {
        if (rebuffer() && (*in = *pos++) == 0) {
          return true;
        }
      }
      ++in;
    }
  }

  inline bool scan(double &in) {
    if (pos + FLT_LEN >= endbuf && !rebuffer()) {
      in = 0.0;
      return false;
    }

#if 1
    char *tmp;
    in = std::strtod(pos, &tmp);
    pos = ++tmp;
    return true;
#else
    constexpr size_t MAX_FIVE_IEXP=27;
    constexpr uint64_t FIVES[MAX_FIVE_IEXP+1]={
      UINT64_C(0x0000000000000001), UINT64_C(0x0000000000000005),
      UINT64_C(0x0000000000000019), UINT64_C(0x000000000000007D),
      UINT64_C(0x0000000000000271), UINT64_C(0x0000000000000C35),
      UINT64_C(0x0000000000003D09), UINT64_C(0x000000000001312D),
      UINT64_C(0x000000000005F5E1), UINT64_C(0x00000000001DCD65),
      UINT64_C(0x00000000009502F9), UINT64_C(0x0000000002E90EDD),
      UINT64_C(0x000000000E8D4A51), UINT64_C(0x0000000048C27395),
      UINT64_C(0x000000016BCC41E9), UINT64_C(0x000000071AFD498D),
      UINT64_C(0x0000002386F26FC1), UINT64_C(0x000000B1A2BC2EC5),
      UINT64_C(0x000003782DACE9D9), UINT64_C(0x00001158E460913D),
      UINT64_C(0x000056BC75E2D631), UINT64_C(0x0001B1AE4D6E2EF5),
      UINT64_C(0x000878678326EAC9), UINT64_C(0x002A5A058FC295ED),
      UINT64_C(0x00D3C21BCECCEDA1), UINT64_C(0x0422CA8B0A00A425),
      UINT64_C(0x14ADF4B7320334B9), UINT64_C(0x6765C793FA10079D),
    };
    constexpr size_t MAX_TEN_IEXP=19;
    constexpr uint64_t TENS[MAX_TEN_IEXP+1]={
      UINT64_C(0x0000000000000001), UINT64_C(0x000000000000000A),
      UINT64_C(0x0000000000000064), UINT64_C(0x00000000000003E8),
      UINT64_C(0x0000000000002710), UINT64_C(0x00000000000186A0),
      UINT64_C(0x00000000000F4240), UINT64_C(0x0000000000989680),
      UINT64_C(0x0000000005F5E100), UINT64_C(0x000000003B9ACA00),
      UINT64_C(0x00000002540BE400), UINT64_C(0x000000174876E800),
      UINT64_C(0x000000E8D4A51000), UINT64_C(0x000009184E72A000),
      UINT64_C(0x00005AF3107A4000), UINT64_C(0x00038D7EA4C68000), 
      UINT64_C(0x002386F26FC10000), UINT64_C(0x016345785D8A0000),
      UINT64_C(0x0DE0B6B3A7640000), UINT64_C(0x8AC7230489E80000),
    };
    auto mp_muladd_1=[](uint64_t *mp, size_t &size, uint64_t mul, uint64_t cy) {
      mp += size;
      size_t i=-size;
      do {
        __uint128_t prod=__uint128_t(mp[i])*mul;
        mp[i] = prod+cy;
        cy = (mp[i]<cy) + (prod>>64);
      } while (++i > 0);
      if (cy) {
        ++size;
        *mp = cy;
      }
    };
    auto mp_geq=[](const uint64_t *lhs, size_t lsize, const uint64_t *rhs,
                   size_t rsize) {
      if (lsize != rsize) return (lsize > rsize);
      size_t i=lsize-1;
      do {
        if (lhs[i] != rhs[i])
          return (lhs[i] > rhs[i]);
      } while (i-- > 0);
      return true;
    };
    auto mp_sub=[](uint64_t *lhs, size_t &lsize, const uint64_t *rhs,
                   size_t rsize) {
      size_t i=-rsize;
      lhs += rsize;
      rhs += rsize;
      uint64_t cy=0;
      do {
        uint64_t tmp=rhs[i]+cy;
        cy = (lhs[i] < tmp);
        lhs[i] -= tmp;
      } while (++i > 0);
      if (cy) --*lhs;
      lhs += lsize-rsize;
      while (lsize > 1) {
        if (*--lhs) break;
        --lsize;
      }
    };
    auto round_away=[](uint64_t is_neg, uint64_t last_bit, uint64_t half_bit,
                       uint64_t more_bits) {
      return half_bit && (last_bit || more_bits);
      // switch (fegetround()) {
      // case FE_DOWNWARD:
      // return is_neg && (half_bit || more_bits);
      // case FE_TONEAREST:
      // return half_bit && (last_bit || more_bits);
      // case FE_TOWARDZERO:
      // return false;
      // case FE_UPWARD:
      // return !is_neg && (half_bit || more_bits);
      // default:
      // assert(0);
      // }
    };
    union { uint64_t lu; double lf; } res;
    constexpr int SIGN_SH=63, EXP_SH=52;
    res.lu = 0;
    if (*pos == '-') {
      ++pos;
      res.lu = UINT64_C(1) << SIGN_SH;
    }
    while (*pos == '0') ++pos;
    uint64_t mantissa=0, exponent=0;
    uint64_t more_bits=0, last_bit=0, half_bit=0;
    if (*pos > '0') {
      uint64_t bigint[16+1]={}, bisize=1;
      uint64_t intpart=*pos-'0';
      int count=1;
      ++pos;
      while (*pos >= '0') {
        intpart = intpart*10 + *pos-'0';
        ++pos;
        if (++count == MAX_TEN_IEXP) break;
      }
      if (*pos < '0') {
        mantissa = intpart;
        int msb=63-__builtin_clzll(mantissa);
        exponent = msb;
        if (msb >= EXP_SH+1) {
          mantissa >>= (msb-(EXP_SH+1));
          if (intpart & ((UINT64_C(1) << (msb-(EXP_SH+1)))-1))
            more_bits = 1;
          if (*pos == '.') {
            while (*++pos == '0') /* nop */;
            if (*pos > '0') {
              more_bits = 1;
              while (*++pos >= '0') /* nop */;
            }
          }
          goto rounding;
          /* NOT REACHED */
        }
        goto parsing_fraction;
        /* NOT REACHED */
      }
      bigint[0] = intpart;
      intpart = *pos-'0';
      count = 1;
      ++pos;
      while (*pos >= '0') {
        intpart = intpart*10 + *pos-'0';
        ++pos;
        if (++count == MAX_TEN_IEXP) {
          mp_muladd_1(bigint, bisize, TENS[MAX_TEN_IEXP], intpart);
          intpart = 0;
          count = 0;
          if (bisize > 16) {
            exponent = 0x3FF;
            mantissa = 0;
            goto rounding;
          }
        }
      }
      if (count)
        mp_muladd_1(bigint, bisize, TENS[count], intpart);
      {
        mantissa = bigint[bisize-1];
        int msb=63-__builtin_clzll(mantissa);
        exponent = (bisize-1) << 6 | msb;
        if (exponent > 0x3FF) {
          exponent = 0x3FF;
          mantissa = 0;
          goto rounding;
        }
        size_t ignored=bisize-1;
        if (bisize > 1) {
          if (msb > EXP_SH+1) {
            mantissa >>= (msb-(EXP_SH+1));
            if (bigint[ignored] & ((UINT64_C(1) << (msb-(EXP_SH+1)))-1))
              more_bits = 1;
          } else if (msb < EXP_SH+1) {
            mantissa <<= ((EXP_SH+1)-msb);
            mantissa |= bigint[bisize-2] >> (64-((EXP_SH+1)-msb));
            if (bigint[--ignored] & ((UINT64_C(1) << (64-((EXP_SH+1)-msb)))-1))
              more_bits = 1;
          } else {
            mantissa = bigint[bisize-1];
          }
          if (more_bits == 0)
            for (size_t i=0; i<ignored; ++i)
              if (bigint[i]) {
                more_bits |= 1;
                break;
              }
        } else {
          mantissa >>= (msb-(EXP_SH+1));
          if (bigint[0] & ((UINT64_C(1) << (msb-(EXP_SH+1)))-1))
            more_bits = 1;
        }
        if (*pos == '.') {
          while (*++pos == '0') /* nop */;
          if (*pos > '0') {
            more_bits = 1;
            while (*++pos >= '0') /* nop */;
          }
        }
        goto rounding;
        /* NOT REACHED */
      }
    }
  parsing_fraction:
    {
      size_t lzero=0;
      int msb=(mantissa? 63-__builtin_clzll(mantissa):0);
      if (*pos != '.') {
        if (mantissa) {
          mantissa <<= ((EXP_SH+1)-msb);
        }
        goto rounding;
      }
      {
        const char *tmp=++pos;
        while (*pos == '0') ++pos;
        lzero = pos - tmp;
        if (*pos < '0') {
          mantissa <<= ((EXP_SH+1)-msb);
          goto rounding;
        }
      }
      if (mantissa == 0 && lzero+1 > 324) {
        if (*pos > '0') {
          more_bits = 1;
          while (*++pos >= '0') /* nop */;
        }
        goto rounding;
      }
      if (mantissa && msb+lzero >= EXP_SH+1) {
        if (*pos > '0') {
          more_bits = 1;
          while (*++pos >= '0') /* nop */;
        }
        mantissa <<= ((EXP_SH+1)-msb);
        goto rounding;
      }
      if (mantissa)
        mantissa <<= lzero;
      {
        uint64_t bigfrac[40+1]={}, bfsize=1;
        uint64_t bigfive[40+1]={1}, psize=1;
        if (mantissa == 0)
          exponent -= lzero;
        mp_muladd_1(bigfive, psize, FIVES[lzero%MAX_FIVE_IEXP], 0);
        for (size_t i=0; i<lzero/MAX_FIVE_IEXP; ++i)
          mp_muladd_1(bigfive, psize, FIVES[MAX_FIVE_IEXP], 0);
        while (*pos >= '0') {
          mp_muladd_1(bigfrac, bfsize, 10, *pos-'0');
          mp_muladd_1(bigfive, psize, 5, 0);
          mantissa? (mantissa<<=1):(--exponent);
          if (mp_geq(bigfrac, bfsize, bigfive, psize)) {
            mp_sub(bigfrac, bfsize, bigfive, psize);
            mantissa |= 1;
          }
          ++pos;
          if (mantissa & (UINT64_C(1) << (EXP_SH+1))) {
            while (*pos == '0') ++pos;
            more_bits |= (*pos >= '0' || bfsize > 1 || bigfrac[0]);
            while (*pos >= '0') ++pos;
            goto rounding;
          }
        }
        while (bfsize > 1 || bigfrac[0]) {
          mp_muladd_1(bigfrac, bfsize, 2, 0);
          mantissa? (mantissa<<=1):(--exponent);
          if (mp_geq(bigfrac, bfsize, bigfive, psize)) {
            mp_sub(bigfrac, bfsize, bigfive, psize);
            mantissa |= 1;
          }
          if (mantissa & (UINT64_C(1) << (EXP_SH+1))) {
            more_bits |= (bfsize > 1 || bigfrac[0]);
            goto rounding;
          }
        }
        msb = 63 - __builtin_clzll(mantissa);
        mantissa <<= ((EXP_SH+1)-msb);
      }
    }
  rounding:
    if (exponent > UINT64_C(0x3FF) && exponent <= -UINT64_C(0x3FF)) {
      if (mantissa & ((UINT64_C(1) << -(exponent+0x3FF))-1))
        more_bits |= 1;
      mantissa >>= -(exponent+0x3FE);
      exponent = -0x3FF;
    }
    half_bit = mantissa & 1;
    mantissa >>= 1;
    last_bit = mantissa & 1;
    if (round_away(res.lu>>SIGN_SH, last_bit, half_bit, more_bits)) {
      if (++mantissa & (UINT64_C(1) << (EXP_SH+1))) {
        ++exponent;
        mantissa >>= 1;
      }
    }
    if (mantissa & (UINT64_C(1) << EXP_SH)) {
      mantissa ^= UINT64_C(1) << EXP_SH;
      res.lu |= (exponent+0x3FF) << EXP_SH;
    }
    if (exponent+0x3FF < 0x800)
      res.lu |= mantissa;
    in = res.lf;
    ++pos;
#endif
    return true;
  }

  template <class Int>
  inline bool scan(Int &in) {
    in = 0;

    // assume that no redundant whitespace appears
    if (pos + INT_LEN >= endbuf && !rebuffer()) {
      return false;
    }

    if (std::is_signed<Int>::value) {
      if (*pos == '-') {
        in = ~*++pos+'1';
        while (*++pos >= '0') {
          in = in*10 + ~*pos+'1';
        }
        ++pos;
        return true;
      }
    }

    // assume that numbers are separated by the character whose value is
    // less than '0' (e.g. whitespaces, newlines)
    do {
      in = in*10 + *pos-'0';
    } while (*++pos >= '0');
    ++pos;
    return true;
  }

  inline bool eat() {
    if (*pos > ' ') {
      return true;
    }

    do {
      if (*pos == 0 && !rebuffer()) {
        return false;
      }
    } while (*++pos <= ' ');

    return true;
  }

  inline bool eat(char ch) {
    if (*pos == ch) {
      return true;
    }

    do {
      if (*pos == 0 && !rebuffer()) {
        return false;
      }
    } while (*++pos != ch);

    return true;
  }

  class Scanner {
    bool rebuffer() {
      return FastIn::rebuffer();
    }

  public:
    Scanner(FILE *fin=stdin) {
      FastIn::fin = fin;
      endbuf = pos + std::fread(buf, 1, BUF_SIZE, fin);
    }

    template <class T>
    inline bool scan(T &in) {
      return FastIn::scan(in);
    }

    template <class First, class... Rest>
    inline bool scan(First &in, Rest &...ins) {
      return scan(in) && scan(ins...);
    }
  };
}

FastIn::Scanner cin;

int main() {
  int m;
  cin.scan(m);

  constexpr double e=exp(1);
  for (int i=0; i<m; ++i) {
    int a, b;
    double t;
    cin.scan(a, b, t);

    if (b == 0) {
      printf("%.12f\n", pow(t, 1.0/a));
      continue;
    }
    if (a == 0) {
      printf("%.12f\n", exp(pow(t, 1.0/b)));
      continue;
    }
    double q=pow(t, 1.0/b)*a/b;
    double lb=std::min(e, q), ub=std::max(e, q);
    for (int i=0; i<50; ++i) {
      double mid=(lb+ub)/2.0;
      (mid*log(mid)<q? lb:ub) = mid;
    }
    printf("%.12f\n", pow(ub, static_cast<double>(b)/a));
  }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード