QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104909 | #2822. 不等式 | lonytree# | WA | 1ms | 5908kb | C++14 | 1.7kb | 2023-05-12 14:17:14 | 2023-05-12 14:17:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
pair<double, pair<int, int> > p[N];
int id[N];
int s1[N << 2];
double s2[N << 2];
void modify(int k, int l, int r, int pos, int v1, double v2)
{
s1[k] += v1;
s2[k] += v1 * v2;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
modify(k << 1, l, mid, pos, v1, v2);
} else {
modify(k << 1 | 1, mid + 1, r, pos, v1, v2);
}
return;
}
double query(int k, int l, int r, int lim)
{
if (l == r) {
return s2[k] * lim / s1[k];
}
int mid = (l + r) >> 1;
if (s1[k << 1] >= lim) {
return query(k << 1, l, mid, lim);
}
return s2[k << 1] + query(k << 1 | 1, mid + 1, r, lim - s1[k << 1]);
}
int fl[N], ts[N];
signed main()
{
int n;
scanf("%d", &n);
for (int i = 1, a, b; i <= n; ++i) {
scanf("%d%d", &a, &b);
if (a == 0) {
fl[i] = 1, ts[i] = b;
a = 1;
}
p[i] = make_pair((double)b / a, make_pair(a, i));
}
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; ++i) {
id[p[i].second.second] = i;
}
double s = 0, tmp = 0, res = 0;
for (int i = 1; i <= n; ++i) {
if (fl[i]) {
res += abs(ts[i]);
} else {
modify(1, 1, n, id[i], p[id[i]].second.first, p[id[i]].first);
s += p[id[i]].second.first;
tmp += p[id[i]].second.first * p[id[i]].first;
}
double pos1 = s < 2 ? 0 : query(1, 1, n, s / 2), pos2 = s < 1 ? 0 : query(1, 1, n, (s + 1) / 2);
printf("%.10lf\n", res + tmp - pos1 - pos2);
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5908kb
input:
1000 61238 60248 73732 -26564 -93007 4478 -39783 -29386 6714 -96099 58853 29344 88517 -7643 -16343 97123 82004 96690 -63916 13672 -72104 -93128 -33526 4108 -5475 -53323 57787 15891 -9523 -10161 -96799 -83119 77140 97223 -56595 -95821 24758 73652 58307 -22694 -62422 2448 59087 -47128 67302 -53844 -61...
output:
0.0000000000 82310.6896327239 3122.6079885039 -6631.2428230837 96073.2157483915 132086.6835505412 183864.1006235876 78592.5102033881 134395.4632219258 44443.6461392127 31677.9853023635 -13666.6862079101 -61603.1974264346 -26817.6985540244 -32230.5478735154 -77869.0000000000 -27742.9419296620 -56833....
result:
wrong answer 2nd numbers differ - expected: '21040.3674840', found: '82310.6896327', error = '2.9120367'