結果
問題 | No.1173 Endangered Species |
ユーザー |
|
提出日時 | 2020-04-28 06:45:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,268 bytes |
コンパイル時間 | 1,127 ms |
コンパイル使用メモリ | 97,340 KB |
最終ジャッジ日時 | 2025-01-10 02:39:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 19 |
ソースコード
#include <iostream> #include <iomanip> #include <string> #include <utility> #include <cassert> #include <algorithm> #include <cmath> #define show(x) std::cout<<#x<<" = "<<(x)<<std::endl #define rep(i,n) for(int i=0;i<(int)(n);++i) #define sar(a,n) {std::cout<<#a<<":";rep(pachico,n)std::cout<<" "<<a[pachico];std::cout<<std::endl;} class Solver { private: static const int MIN_N = 1; static const int MAX_N = 1000; static const int NUM_DECIMAL_P = 5; static const int NUM_DECIMAL_Q = 5; static const int MIN_P = 0; // depends on NUM_DECIMAL_P static const int MAX_P = 100000; // depends on NUM_DECIMAL_P static const int SUM_P = 100000; // depends on NUM_DECIMAL_P static const int MIN_Q= 10000; // depends on NUM_DECIMAL_Q static const int MAX_Q = 90000; // depends on NUM_DECIMAL_Q static const int MIN_A = 0; static const int MAX_A = 10; enum message { CORRECT, ERROR }; int N; double *p, *q; int *A; double answer; public: Solver(){} ~Solver(); void operator()(); private: void input(); message check_int_range(const int value, const int MIN_VAL, const int MAX_VAL); // [MIN_VAL, MAX_VAL] std::pair<int, message> scan_integer(const int MIN_VAL, const int MAX_VAL); // [MIN_VAL, MAX_VAL] std::pair<double, message> scan_floating_point (const int NUM_DECIMAL, const int MIN_VAL, const int MAX_VAL, int& check_sum); message scan_N(); message scan_p(); std::pair<double, message> scan_p_element(int& sum); message scan_q(); std::pair<double, message> scan_q_element(); message scan_A(); void solve(); double solve_impl(); void output(); }; Solver::~Solver() { delete[] p; delete[] q; delete[] A; } void Solver::operator()() { solve(); } void Solver::input() { const auto flag_N = scan_N(); if(flag_N == ERROR) assert(false); const auto flag_p = scan_p(); if(flag_p == ERROR) assert(false); const auto flag_q = scan_q(); if(flag_q == ERROR) { delete[] p; assert(false); } const auto flag_A = scan_A(); if(flag_A == ERROR) { delete[] p; delete[] q; assert(false); } } Solver::message Solver::check_int_range(const int value, const int MIN_VAL, const int MAX_VAL) { return (value < MIN_VAL || value > MAX_VAL) ? ERROR : CORRECT; } std::pair<int, Solver::message> Solver::scan_integer(const int MIN_VAL, const int MAX_VAL) { std::string s; std::cin >> s; const int value = std::stoi(s); const Solver::message mes = check_int_range(value, MIN_VAL, MAX_VAL); return {value, mes}; } std::pair<double, Solver::message> Solver::scan_floating_point (const int NUM_DECIMAL, const int MIN_VAL, const int MAX_VAL, int& check_sum) { std::string s; std::cin >> s; if((int)s.size() != NUM_DECIMAL + 2) return {0.0, ERROR}; double value = 0.0, digit = 1.0; int check_value = 0; Solver::message mes = CORRECT; for(int i = 0; i < (int)s.size(); ++i) { if(i == 1) { if(s[i] != '.') { mes = ERROR; break; } } else { if(isdigit(s[i])) { value += digit * (int)(s[i] - '0'); digit *= 0.1; check_value = check_value * 10 + (int)(s[i] - '0'); } else { mes = ERROR; break; } } } if(check_int_range(check_value, MIN_VAL, MAX_VAL) == ERROR) mes = ERROR; check_sum += check_value; return {value, mes}; } Solver::message Solver::scan_N() { const auto [value, mes] = scan_integer(MIN_N, MAX_N); if(mes == CORRECT) N = value; return mes; } Solver::message Solver::scan_p() { p = new double[N]; int sum = 0; Solver::message mes = CORRECT; for(int i = 0; i < N; ++i) { const auto [value, tmp_mes] = scan_p_element(sum); if(tmp_mes == ERROR) { mes = ERROR; break; } p[i] = value; } if(sum != SUM_P) mes = ERROR; if(mes == ERROR) delete[] p; return mes; } std::pair<double, Solver::message> Solver::scan_p_element(int& sum) { return scan_floating_point(NUM_DECIMAL_P, MIN_P, MAX_P, sum); } Solver::message Solver::scan_q() { q = new double[N]; int ignore = 0; Solver::message mes = CORRECT; for(int i = 0; i < N; ++i) { const auto [value, tmp_mes] = scan_q_element(); if(tmp_mes == ERROR) { mes = ERROR; break; } q[i] = value; } if(mes == ERROR) delete[] q; return mes; } std::pair<double, Solver::message> Solver::scan_q_element() { int ignore = 0; return scan_floating_point(NUM_DECIMAL_Q, MIN_Q, MAX_Q, ignore); } Solver::message Solver::scan_A() { A = new int[N]; Solver::message mes = CORRECT; for(int i = 0; i < N; ++i) { const auto [value, tmp_mes] = scan_integer(MIN_A, MAX_A); if(tmp_mes == ERROR) { mes = ERROR; break; } A[i] = value; } if(mes == ERROR) delete[] A; return mes; } void Solver::solve() { int N; double *p, *q; int *A; input(); answer = solve_impl(); output(); } double Solver::solve_impl() { double l = 0.0, r = 1.0; auto f = [&](const double x) { double result = x; for(int i = 0; i < N; ++i){ result -= p[i] * (1 - q[i]) / (1 - q[i] * x); } return result; }; for(int i = 0; i < 60; ++i){ double mid = (l + r) / 2; if(f(mid) < 0.0){ l = mid; }else{ r = mid; } } double result = 0.0; for(int i = 0; i < N; ++i){ result += A[i] * log((1 - q[i]) / (1 - q[i] * l)); } return result; } void Solver::output() { std::cout << std::fixed << std::setprecision(12) << answer << std::endl; } void func() { class Solver solver; solver(); } int main() { func(); return 0; }