QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#401091#5433. Absolute DifferencecomeintocalmWA 1ms4096kbC++204.2kb2024-04-27 21:44:232024-04-27 21:44:25

Judging History

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

  • [2024-04-27 21:44:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4096kb
  • [2024-04-27 21:44:23]
  • 提交

answer

#include <bits/stdc++.h>

using db = double;

int main() {
    // freopen("in", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    std::vector<std::pair<int,int>> a(n), b(m);
    std::vector<std::pair<int,int>> sa, sb;
    bool fa = false, fb = false;
    long long suma = 0, sumb = 0;
    for (auto &[x, y] : a) {
        scanf("%d%d", &x, &y);
        suma += y - x;
        if (x != y) {
            fa = true;
        }
    }
    for (auto &[x, y] : b) {
        scanf("%d%d", &x, &y);
        sumb += y - x;
        if (x != y) {
            fb = true;
        }
    }
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    int l = -1;
    for (auto &&[x, y]: a) {
        int r = l;
        while (r + 1 < m && b[r + 1].first < y) {
            ++r;
        }
        for (int i = l + 1; i <= r && l < r; ++i) {
            if (b[i].second <= x) {
                sa.emplace_back(b[i]);
                ++l;
                continue;
            }
            if (b[i].first < x) {
                sb.emplace_back(b[i].first, x);
                b[i].first = x;
            }
            if (b[i].first > x) {
                sa.emplace_back(x, b[i].first);
                x = b[i].first;
            }
            if (b[i].second > x) {
                sa.emplace_back(x, y);
                sb.emplace_back(x, y);
                x = y;
                b[i].first = y;
            } else {
                sa.emplace_back(b[i]);
                sb.emplace_back(b[i]);
                x = b[i].second;
                b[i].first = b[i].second;
                ++l;
            }
        }
        if (x < y) {
            sa.emplace_back(x, y);
        }
    }
    for (int r = l + 1; r < m; ++r) {
        if (b[r].first < b[r].second) {
            sb.emplace_back(b[r]);
        }
    }
    double ans = 0;
    n = sa.size(), m = sb.size();
    // std::cout << n << ' ' << m << '\n';
    std::vector<long long> prea, pre1(n), pre2(n);

    auto get = [] (int l, int r, std::vector<long long> &pre) -> long long {
        if (l > r) {
            return 0;
        }
        if (l == 0) {
            return pre[r];
        }
        return pre[r] - pre[l - 1];
    };

    if (!fa && fb) {
        std::swap(fa, fb);
        std::swap(a, b);
    }
    if (!fb) {
        n = a.size();
        prea.assign(n, 0);
        for (int i = 0; i < n; ++i) {
            prea[i] = (a[i].second + a[i].first);
            if (i > 0) {
                prea[i] += prea[i - 1];
            }
        }
        // puts("q");
        for (auto &[l1, r1]: b) {
            int p = std::lower_bound(a.begin(), a.end(), std::make_pair(l1, r1)) - a.begin();
            // printf("p %d\n", p);
            ans += (1ll * (p) * l1 - get(0, p - 1, prea) / 2.0);
            if (p < m) {
                ans += (get(p, m - 1, prea) / 2.0 - 1ll * (m - p) * l1);
            }
        }
    } else {
        for (int i = 0; i < n; ++i) {
            pre1[i] = (sa[i].second - sa[i].first);
            pre2[i] = 1ll * sa[i].second * sa[i].second - 1ll * sa[i].first * sa[i].first;
            if (i > 0) {
                pre1[i] += pre1[i - 1];
                pre2[i] += pre2[i - 1];
            }
        }
        for (auto &[l1, r1]: sb) {
            int p = std::lower_bound(sa.begin(), sa.end(), std::make_pair(l1, r1)) - sa.begin();
            bool flag = false;
            if (p < m) {
                auto &[l2, r2] = sa[p];
                if (l1 == l2 && r1 == r2) {
                    ans += (r1 - l1) / 3.0;
                    ++p;
                    flag = true;
                }
            }
            if (p < m) {
                ans += ((db)(r1 - l1) * get(p - 1, m - 1, pre2) - (db)(1ll * r1 * r1 - 1ll * l1 * l1) * get(p - 1, m - 1, pre1)) / 2.0;
            }
            if (flag) {
                --p;
            }
            if (p > 0) {
                ans += ((db)(1ll * r1 * r1 - 1ll * l1 * l1) * get(0, p - 1, pre1) - (db)(r1 - l1) * get(0, p - 1, pre2)) / 2.0;
            }
        }
        ans /= suma;
        ans /= sumb;
    }
    printf("%.16lf\n", ans);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3804kb

input:

1 1
0 1
0 1

output:

0.3333333333333333

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.5000000000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

0.0000000001666667

result:

wrong answer 1st numbers differ - expected: '666666666.6666666', found: '0.0000000', error = '1.0000000'