QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104912#2822. 不等式lonytree#WA 5ms11736kbC++141.8kb2023-05-12 14:28:102023-05-12 14:28:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 14:28:11]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:11736kb
  • [2023-05-12 14:28:10]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

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("%lld", &n);
    for (int i = 1, a, b; i <= n; ++i) {
        scanf("%lld%lld", &a, &b);
        if (a == 0) {
            fl[i] = 1, ts[i] = b;
            a = 1;
        }
        if (a < 0) {
            a = -a, b = -b;
        }
        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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 11736kb

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
86210.4524605675
117511.8811272270
213287.6227488253
245465.2130592321
248846.3927016246
345182.5276914641
445820.7672003183
456415.4090659843
553014.9941294742
555508.8207016676
609095.4250540282
627287.5359509925
634829.7809888037
691329.7679062765
751826.7525189880
8...

result:

wrong answer 2nd numbers differ - expected: '21040.3674840', found: '82310.6896327', error = '2.9120367'