QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#591789#5433. Absolute Differencepengpeng_fudan#WA 3ms18448kbC++145.8kb2024-09-26 17:49:212024-09-26 17:49:22

Judging History

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

  • [2024-09-26 17:49:22]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:18448kb
  • [2024-09-26 17:49:21]
  • 提交

answer

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

using namespace std;

const int N = 3e5 + 10;
int n, m;
long double al[N], ar[N], bl[N], br[N];
long double s2[N], s1[N], s0[N];
long double ans;

long double calc(const long double *a, const long double *b) {
    vector<pair<long double, int>> c;
    for (int i = 1; i <= n; ++i) {
        c.emplace_back(a[i], 0);
    }
    for (int i = 1; i <= m; ++i) {
        c.emplace_back(b[i], 1);
    }
    sort(c.begin(), c.end());
    long double sa0 = 0, sa1 = 0, sa2 = 0, sa3 = 0, sb0 = 0, sb1 = 0, sb2 = 0, sb3 = 0;
    long double res = 0;
    for (int i = 0; i < n + m; ++i) {
        if (c[i].second == 0) {
            sa0 += 1.0;
            sa1 += c[i].first;
            sa2 += c[i].first * c[i].first;
            sa3 += c[i].first * c[i].first * c[i].first;
            res += -sb3 + 3.0 * sb2 * c[i].first - 3.0 * sb1 * c[i].first * c[i].first + sb0 * c[i].first * c[i].first * c[i].first;
        }
        else {
            sb0 += 1.0;
            sb1 += c[i].first;
            sb2 += c[i].first * c[i].first;
            sb3 += c[i].first * c[i].first * c[i].first;
            res += -sa3 + 3.0 * sa2 * c[i].first - 3.0 * sa1 * c[i].first * c[i].first + sa0 * c[i].first * c[i].first * c[i].first;
        }
    }
    return res;
}

long double lsh[N];

long double calc2(vector<pair<long double, long double>> q) {
    sort(q.begin(), q.end());
    int tot = 0;
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second == -1) {
            lsh[++tot] = q[i].first;
        }
        else {
            lsh[++tot] = q[i].second;
            lsh[++tot] = q[i].first;
        }
    }
    sort(lsh + 1, lsh + tot + 1);
    for (int i = 0; i <= tot; ++i) {
        s0[i] = s1[i] = s2[i] = 0;
    }
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second == -1) {
            int j = lower_bound(lsh + 1, lsh + tot + 1, q[i].first) - lsh;
            s0[j] += 1.0;
            s1[j] += q[i].first;
            s2[j] += q[i].first * q[i].first;
        }
    }
    for (int i = 1; i <= tot; ++i) {
        s0[i] += s0[i - 1];
        s1[i] += s1[i - 1];
        s2[i] += s2[i - 1];
    }
    long double res = 0;
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second != -1) {
            long double l = q[i].first, r = q[i].second;
            int il = lower_bound(lsh + 1, lsh + tot + 1, l) - lsh;
            int ir = lower_bound(lsh + 1, lsh + tot + 1, r) - lsh;
            res += r * r * s0[il] - l * l * s0[il] - 2.0 * s1[il] * r + 2.0 * s1[il] * l;
            res += (l * l + r * r) * (s0[ir] - s0[il]) + 2.0 * (s2[ir] - s2[il]) - 2.0 * (l + r) * (s1[ir] - s1[il]);
            res += (l * l - r * r) * (s0[tot] - s0[ir]) + 2.0 * (r - l) * (s1[tot] - s1[ir]);
        }
    }
    return res;
}

// long double calc3()

signed main() {
    long long _n, _m;
    scanf("%lld%lld", &_n, &_m);
    n = _n, m = _m;
    for (int i = 1; i <= n; ++i) {
        // int l, r;
        scanf("%lld%lld", &_n, &_m);
        al[i] = _n, ar[i] = _m;
    }
    // cerr << 1 << '\n';
    // return 0;
    for (int i = 1; i <= m; ++i) {
        // int l, r;
        scanf("%lld%lld", &_n, &_m);
        bl[i] = _n, br[i] = _m;
    }
    int sa = 0, sb = 0;
    for (int i = 1; i <= n; ++i) {
        sa += ar[i] - al[i];
    }
    for (int i = 1; i <= m; ++i) {
        sb += br[i] - bl[i];
    }
    if (sa && sb) {
        ans += calc(al, br);
        ans -= calc(al, bl);
        ans += calc(ar, bl);
        ans -= calc(ar, br);
        // cerr << ans << '\n';
        // cout << (int) ans << '\n';
        
        // cerr << sa << ' ' << sb << '\n';
        long double Ans = (long double) ans;
        // cerr << Ans << '\n';
        Ans /= 6.0;
        Ans /= (long double) sa;
        Ans /= (long double) sb;
        printf("%.15Lf\n", Ans);
    }
    else if (sa && !sb) {
        vector<pair<long double, long double>> q;
        for (int i = 1; i <= n; ++i) {
            q.emplace_back(al[i], ar[i]);
        }
        for (int i = 1; i <= m; ++i) {
            q.emplace_back(bl[i], -1);
        }
        ans = calc2(q);
        long double Ans = (long double) ans;
        Ans /= 2.0;
        Ans /= (long double) sa;
        Ans /= (long double) m;
        printf("%.15Lf\n", Ans);
    }
    else if (!sa && sb) {
        vector<pair<long double, long double>> q;
        for (int i = 1; i <= n; ++i) {
            q.emplace_back(al[i], -1);
        }
        for (int i = 1; i <= m; ++i) {
            q.emplace_back(bl[i], br[i]);
        }
        ans = calc2(q);
        long double Ans = (long double) ans;
        Ans /= 2.0;
        Ans /= (long double) sb;
        Ans /= (long double) n;
        printf("%.15Lf\n", Ans);
    }
    else if (!sa && !sb) {
        vector<pair<long double, int>> q;
        for (int i = 1; i <= n; ++i) {
            q.emplace_back(al[i], 0);
        }
        for (int i = 1; i <= m; ++i) {
            q.emplace_back(bl[i], 1);
        }
        sort(q.begin(), q.end());
        long double sa0 = 0, sa1 = 0, sb0 = 0, sb1 = 0;
        for (int i = 0; i < n + m; ++i) {
            // cerr << (int)q[i].first << '\n';
            if (q[i].second == 0) {
                sa0 += 1.0;
                sa1 += q[i].first;
                ans += sb0 * q[i].first - sb1;
            }
            if (q[i].second == 1) {
                sb0 += 1.0;
                sb1 += q[i].first;
                ans += sa0 * q[i].first - sa1;
                // cerr << (int)sa0 << ' ' << (int)sa1 << '\n';
            }
        }
        long double Ans = (long double) ans;
        Ans /= (long double) n;
        Ans /= (long double) m;
        printf("%.15Lf\n", Ans);
    }

    return 0;
}

详细

Test #1:

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

input:

1 1
0 1
0 1

output:

0.333333333333333

result:

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

Test #2:

score: 0
Accepted
time: 3ms
memory: 18448kb

input:

1 1
0 1
1 1

output:

0.500000000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686069

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000058208

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000523869

result:

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

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000000

result:

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

Test #9:

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

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:

6717.117145739453736

result:

ok found '6717.117145739', expected '6717.117145739', error '0.000000000'

Test #10:

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

input:

1000 1000
-5010 -4999
-2128 -2113
-5798 -5765
705 713
-3956 -3938
-5308 -5307
6759 6772
-772 -770
-860 -859
2308 2323
-5500 -5500
5140 5177
-6747 -6733
7509 7511
8864 8870
-6382 -6374
1901 1904
-5763 -5760
3019 3027
2962 2963
-314 -301
-222 -203
-726 -724
-62 -58
-1203 -1195
-5216 -5215
-4298 -4292
...

output:

6682.581127471435668

result:

ok found '6682.581127471', expected '6682.581127471', error '0.000000000'

Test #11:

score: -100
Wrong Answer
time: 3ms
memory: 18296kb

input:

1000 1000
770 770
5869 5869
-8786 -8786
7549 7549
-4165 -4165
4023 4023
-9779 -9779
7797 7797
1105 1105
508 508
7653 7653
-359 -359
9393 9393
-9363 -9363
-4160 -4160
-3682 -3682
9409 9409
-8548 -8548
-9908 -9908
-7494 -7494
3751 3751
2326 2326
-3311 -3311
3651 3651
-7663 -7663
5376 5376
-7071 -7071
...

output:

6678.318902555742532

result:

wrong answer 1st numbers differ - expected: '6673.7568169', found: '6678.3189026', error = '0.0006836'