QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717593#5433. Absolute DifferenceHygebraWA 2ms12116kbC++146.6kb2024-11-06 18:26:212024-11-06 18:26:22

Judging History

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

  • [2024-11-06 18:26:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12116kb
  • [2024-11-06 18:26:21]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
    using namespace std;
    const int N = 500005;
    const int INF = 2e9;
    pair<int, int> a[N], b[N], x[N], y[N];
    double w[N], g[N], f[N];
signed main() {
    int n = 0, m = 0;
    bool flagn = false, flagm = false;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i].first, &a[i].second);
        if (a[i].first < a[i].second)
            flagn = true;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld", &b[i].first, &b[i].second);
        if (b[i].first <  b[i].second)
            flagm = true;
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    //printf("114514----\n");
    if (!flagn && !flagm) {
        for (int i = 1; i <= m; i++)
            w[i] = w[i - 1] + b[i].first;
        double ans = 0;
        for (int i = 1, j = 1; i <= n; i++) {
            while (j <= m && b[j].first < a[i].first)
                j++;
            ans += (double)((double)a[i].first * (j - 1) - w[j - 1]) / ((double)n * m);
            ans += (double)(w[m] - w[j - 1] - (double)a[i].first * (m - j + 1))/ ((double)n * m);
        }
        printf("%.11f\n", ans);
        return 0;
    }
    //printf("191810\n");
    if (flagn && !flagm) {
        for (int i = 1; i <= max(n, m); i++)
            swap(a[i], b[i]);
        swap(n, m), swap(flagn, flagm);
    }

    if (!flagn && flagm) {
         for (int i = 1; i <= m; i++) {
            w[i] = w[i - 1];
            if (b[i].first < b[i].second)
                w[i] += (double)(b[i].second + b[i].first) * (b[i].second - b[i].first);
            g[i] = g[i - 1] + (b[i].second - b[i].first);
        }
        double ans = 0;
        for (int i = 1, j = 1; i <= n; i++) {
            while (j <= m && b[j].second <= a[i].first)
                j++;
            if (j <= m && b[j].first < a[i].first) {
                ans += ((double)2 * a[i].first * (j - 1) * g[j - 1] - w[j - 1]) / 2.0  / g[m] / n;
                ans += (w[m] - w[j] - (double)2 * a[i].first * (m - j) * (g[m] - g[j])) / 2.0  / g[m] / n;
                ans += ((double)2 * a[i].first - (a[i].first + b[j].first)) / 2.0 * ((double)(a[i].first - b[j].first) / g[m]) / n;
                ans += ((double)a[i].first + b[j].second - 2 * a[i].first) / 2.0 * ((double)(b[j].second - a[i].first) / g[m]) / n;
            } else {
                ans += ((double)2 * a[i].first * (j - 1) * g[j - 1]- w[j - 1]) / 2.0 / g[m] / n;
                ans += (w[m] - w[j - 1] - (double)2 * a[i].first * (m - j + 1) * (g[m] - g[j - 1])) / 2.0  / g[m] / n;
            }
        }
        printf("%.11f\n", ans);
        return 0;
    }
    
    
    int u = 1, v = 1, tn = 0, tm = 0;
    x[0] = y[0] = make_pair(-INF,-INF);
    while (u <= n || v <= m) {
        if (u <= n && a[u].first == a[u].second) {
            u++; continue;
        }
        if (v <= m && b[v].first == b[v].second) {
            v++; continue;
        }

        if (u <= n && v > m)
            tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second), u++;
        else if (u <= n && v <= m && a[u] <= b[v] && a[u].second <= b[v].first)
            tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second), u++;
        else if (u <= n && v <= m && a[u] <= b[v] && a[u].second > b[v].first) {
            if (a[u] == b[v]) {
                tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second);
                tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second);
                u++, v++;
            } else if (a[u].first == b[v].first) {
                tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second);
                tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), a[u].second);
                b[v].first = a[u].second;
                u++;
            } else {
                tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), b[v].first);
                a[u].first = b[v].first;
            }
        }
        else if (v <= m && u > n)
            tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second), v++;
        else if (v <= m && u <= n && b[v] <= a[u] && b[v].second <= a[u].first)
            tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second), v++;
        else {
            if (a[u] == b[v]) {
                tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second);
                tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second);
                u++, v++;
            } else if (a[u].first == b[v].first) {
                tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), b[v].second);
                tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second);
                a[u].first = b[v].second;
                v++;
            } else {
                tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), a[u].first);
                b[v].first = a[u].first;
            }
        }
       // printf("%d %d %d %d\n", u, v, tn, tm);
    }
    for (int i = 1; i <= tm; i++) {
        //if (y[i].first < y[i].second)
            w[i] = w[i - 1] + (double)(y[i].first + y[i].second) * (y[i].second - y[i].first);
        g[i] = g[i - 1] + (y[i].second - y[i].first);
    }
    for (int i = 1; i <= tn; i++) {
        f[i] = f[i - 1] + (x[i].second - x[i].first);
    }
    //printf("-------\n");
    double ans = 0;
    for (int i = 1, j = 1; i <= tn; i++) {
        while (j <= tm && y[j].first < x[i].first)
            j++;
        //cout << j << " ---------\n";
        if (j <= tm && y[j] == x[i]) {
            //cout << f[tn] << " " << g[tm] << "   ---\n";
            ans += (x[i].second - x[i].first) / 3.0 * (x[i].second - x[i].first) / f[tn] * (y[i].second - y[i].first) / g[tm];
            ans += ((double)(x[i].second + x[i].first) * (j - 1) * g[j - 1] - w[j - 1]) / 2.0 * (x[i].second - x[i].first) / f[tn] / g[tm];
            ans += (w[tm] - w[j] - (double)(x[i].second + x[i].first) * (tm - j) * (g[tm] - g[j])) / 2.0 * (x[i].second - x[i].first) / f[tn]  / g[tm];
        } else {
            ans += ((double)(x[i].second + x[i].first) * (j - 1) * g[j] - w[j - 1]) / 2.0 * (x[i].second - x[i].first) / f[tn] / g[tm];
            ans += (w[tm] - w[j - 1] - (double)(x[i].second + x[i].first) * (tm - j + 1) * (g[tm] - g[j - 1])) / 2.0 * (x[i].second - x[i].first) / f[tn]  / g[tm];
        }
        
    }  
    printf("%.11f", ans);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11952kb

input:

1 1
0 1
0 1

output:

0.33333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

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

input:

1 1
0 1
1 1

output:

0.50000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666662693

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 12072kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.00000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7972kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.00000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 8052kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7964kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000000

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 8044kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.00000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

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

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

5743755.56122355536

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '5743755.5612236', error = '854.0923613'