QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604022#5433. Absolute DifferenceSCUTkkWA 1ms3940kbC++204.4kb2024-10-01 22:11:402024-10-01 22:11:41

Judging History

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

  • [2024-10-01 22:11:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3940kb
  • [2024-10-01 22:11:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i64 = long long;
using pii = pair<int, int>;
using db = double;

#define cY cout << "YES\n"
#define cN cout << "NO\n"
#define cA cout << ans << "\n"
#define pb push_back

const int N = 2e5 + 7;
const ll mod = 998244353;
const ll MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

#define int ll

struct P {
    int l, r, len;

    bool operator<(P a) {
        if (l != a.l)
            return l < a.l;
        return r < a.r;
    }
};

void crossparallel() {
    int n, m;
    cin >> n >> m;

    int la = 0, lb = 0;
    vector<P> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].len = a[i].r - a[i].l;
        la += a[i].r - a[i].l;
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i].l >> b[i].r;
        b[i].len = b[i].r - b[i].l;
        lb += b[i].r - b[i].l;
    }

    if (la == 0) {
        la += n;
        for (auto &i : a) i.len++;
    }
    if (lb == 0) {
        lb += m;
        for (auto &i : b) i.len++;
    }

    // cerr << la << " " << lb << "\n";

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    db ans = 0;

    for (int i = 0, j = 0; i < n; i++) {
        while (j < m && b[j].l < a[i].r) {
            if (a[i].l <= b[j].l && a[i].r >= b[j].r) {
                ans += 1.0 / 3.0 * b[j].len / la * b[j].len / lb * b[j].len;
                a.push_back({a[i].l, b[j].l, b[j].l - a[i].l});
                a[i].len -= b[j].r - a[i].l, a[i].l = b[j].r;
                b[j].len -= b[i].r - b[i].l;
            } else if (a[i].l >= b[j].l && a[i].r <= b[j].r) {
                ans += 1.0 / 3.0 * a[i].len / la * a[i].len / lb * a[i].len;
                b.push_back({b[j].l, a[i].l, a[i].l - b[j].l});
                b[j].len -= a[i].r - b[j].l, b[j].l = a[i].r;
                a[i].len -= a[i].r - a[i].l;
                j--;
                break;
            } else if (a[i].l <= b[j].l && a[i].r <= b[j].r && b[i].l <= a[i].r) {
                ans += 1.0 / 3.0 * (b[j].len - (b[j].r - a[i].r)) / la * (b[j].len - (b[j].r - a[i].r)) / lb * (b[j].len - (b[j].r - a[i].r));
                a.push_back({a[i].l, b[j].l, b[j].l - a[i].l});
                a[i].len -= a[i].r - a[i].l;
                swap(a[i].r, b[j].l);
                b[j].len = b[j].r - b[j].l;
                j--;
                break;
            } else if (a[i].l >= b[j].l && a[i].r >= b[j].r && a[i].l <= b[i].r) {
                ans += 1.0 / 3.0 * (a[i].len - (a[i].r - b[j].r)) / la * (a[i].len - (a[i].r - b[j].r)) / lb * (a[i].len - (a[i].r - b[j].r));
                b.push_back({b[j].l, a[i].l, a[i].l - b[j].l});
                b[j].len -= b[i].r - b[i].l;
                swap(b[j].r, a[i].l);
                a[i].len = a[i].r - a[i].l;
            }
            j++;
        }
    }

    // cerr << ans << "\n";

    vector<P> aa, bb;
    la = 0, lb = 0;

    for (auto &i : a) {
        if (i.len) {
            // cerr << i.l << " " << i.r << " " << i.len << "\n";
            aa.push_back(i);
            la += i.len;
        }
    }
    for (auto &i : b) {
        if (i.len) {
            // cerr << i.l << " " << i.r << " " << i.len << "\n";
            bb.push_back(i);
            lb += i.len;
        }
    }

    n = aa.size(), m = bb.size();
    sort(aa.begin(), aa.end());
    sort(bb.begin(), bb.end());

    db l = 0, r = 0;
    int lenl = 0, lenr = 0;
    for (int i = 0; i < m; i++) {
        r += 1.0 * (bb[i].l + bb[i].r) / 2.0 * bb[i].len;
        lenr += bb[i].len;
    }

    // cerr << lenl << " " << lenr << "\n";
    // cerr << fixed << setprecision(10) << l << " " << r << "\n";

    for (int i = 0, j = 0; i < n; i++) {
        while (j < m && bb[j].l < aa[i].r) {
            lenl += bb[j].len;
            lenr -= bb[j].len;
            l += 1.0 * (bb[j].l + bb[j].r) / 2.0 * bb[j].len;
            r -= 1.0 * (bb[j].l + bb[j].r) / 2.0 * bb[j].len;
            j++;
        }
        ans += 1.0 * aa[i].len / la * (r - l + 1.0 * (lenl - lenr) * (aa[i].l + aa[i].r) / 2.0) / lb;
    }

    cout << fixed << setprecision(20) << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        crossparallel();
    }
    return 0;
}

详细

Test #1:

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

input:

1 1
0 1
0 1

output:

0.33333333333333331483

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.50000000000000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666662693023681641

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.00000000000000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.00000000000000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000000000000000

result:

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

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.00000000000000000000

result:

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

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 3940kb

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:

6638.66174749258698284393

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '6638.6617475', error = '0.0116799'