QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#843527#9966. High Jumpucup-team139#WA 0ms3912kbC++232.8kb2025-01-04 19:59:012025-01-04 19:59:11

Judging History

你现在查看的是最新测评结果

  • [2025-01-04 19:59:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3912kb
  • [2025-01-04 19:59:01]
  • 提交

answer

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <climits>
#include <iomanip>
using namespace std;

using ll = long double;
struct Line
{ // tested with $N,Q\leq 2\cdot 10^5$ (296 ms)
  mutable ll k, m, p;
  int id;
  bool operator<(const Line &o) const { return k < o.k; }
  bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>>
{
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  ll inf = 1 / .0;
  ll div(ll a, ll b)
  { // floored division
    return a / b;
  }
  bool isect(iterator x, iterator y)
  {
    if (y == end())
      return x->p = inf, 0;
    if (x->k == y->k)
      x->p = x->m > y->m ? inf : -inf;
    else
      x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(ll k, ll m, int id)
  {
    auto z = insert({k, m, 0, id}), y = z++, x = y;
    while (isect(y, z))
      z = erase(z);
    if (x != begin() && isect(--x, y))
      isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p)
      isect(x, erase(y));
  }
  pair<ll, int> query(ll x)
  {
    assert(!empty());
    auto l = *lower_bound(x);
    return {l.k * x + l.m, l.id};
  }
};

void solve([[maybe_unused]] int t)
{
  int n;
  cin >> n;
  LineContainer ds;

  int last = 0;
  vector<int> sol;
  vector<long double> p(n + 1);

  for (int i = 1; i <= n; i++)
  {
    cin >> p[i];

    if (p[i] == 1)
    {
      last = i;
      sol.push_back(i);
      continue;
    }

    long double coeff = p[i] / (1 - p[i]);
    ds.add(-coeff, i * coeff, i);

    // cout << i * coeff << " val\n";
  }

  long double ans = 0;
  while (ds.size() > 0 && ds.query(last).first > 0)
  {
    sol.push_back(ds.query(last).second);
    last = sol.back();
  }

  long double prob = 1.0;
  last = 0;
  for (auto i : sol)
  {
    assert(i > last);
    ans += last * prob * (1 - p[i]);
    last = i;
    prob *= p[i];
  }
  ans += last * prob;

  // for (auto i : sol)
  //   cout << i << " ecco\n";

  cout << fixed << setprecision(18) << ans << "\n";
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n = 1;
  // cin >> n;
  for (int i = 1; i <= n; i++)
    solve(i);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3704kb

input:

5
0.9 0.85 0.6 0.456000 0.000000017

output:

2.475200006589200000

result:

ok found '2.4752000', expected '2.4752000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

1
0.000000001

output:

0.000000001000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

2
0.828496829 0.645649353

output:

1.363415270606401637

result:

ok found '1.3634153', expected '1.3634153', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

3
0.551197930 0.393255768 0.207104323

output:

0.867956505597485064

result:

ok found '0.8679565', expected '0.8679565', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

4
0.795361966 0.464795612 0.331129862 0.063526593

output:

1.338829040056732027

result:

ok found '1.3388290', expected '1.3388290', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

5
0.895888800 0.546833708 0.412641158 0.222811308 0.111288348

output:

1.726785711700683739

result:

ok found '1.7267857', expected '1.7267857', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 3912kb

input:

6
0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978

output:

3.778606718507676562

result:

wrong answer 1st numbers differ - expected: '3.8259383', found: '3.7786067', error = '0.0123712'