QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#843522 | #9966. High Jump | ucup-team139# | WA | 0ms | 3968kb | C++23 | 2.8kb | 2025-01-04 19:56:27 | 2025-01-04 19:56:27 |
Judging History
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 << setprecision(20) << 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);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3960kb
input:
5 0.9 0.85 0.6 0.456000 0.000000017
output:
2.4752000065892000001
result:
ok found '2.4752000', expected '2.4752000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1 0.000000001
output:
9.9999999999999999998e-10
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
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: 3896kb
input:
3 0.551197930 0.393255768 0.207104323
output:
0.86795650559748506393
result:
ok found '0.8679565', expected '0.8679565', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3780kb
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: 3968kb
input:
5 0.895888800 0.546833708 0.412641158 0.222811308 0.111288348
output:
1.7267857117006837394
result:
ok found '1.7267857', expected '1.7267857', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3780kb
input:
6 0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978
output:
3.7786067185076765615
result:
wrong answer 1st numbers differ - expected: '3.8259383', found: '3.7786067', error = '0.0123712'