QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139730#5433. Absolute Differencexcyle#WA 1ms5880kbC++203.1kb2023-08-14 12:46:252023-08-14 12:46:28

Judging History

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

  • [2023-08-14 12:46:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5880kb
  • [2023-08-14 12:46:25]
  • 提交

answer

/*

_/      _/       _/_/_/      _/      _/    _/           _/_/_/_/_/
 _/    _/      _/      _/     _/    _/     _/           _/
  _/  _/      _/               _/  _/      _/           _/
   _/_/       _/                 _/        _/           _/_/_/_/
  _/  _/      _/                 _/        _/           _/
 _/    _/      _/      _/        _/        _/           _/
_/      _/       _/_/_/          _/        _/_/_/_/_/   _/_/_/_/_/

*/
#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define ld long double
#define maxn 200005
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int read() {
    int x = 0, w = 0; char ch = getchar();
    while(!isdigit(ch)) w |= ch == '-', ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return w ? -x : x;
}
int n, m, tmp[maxn], tot, suma, sumb, la[maxn], lb[maxn], ra[maxn], rb[maxn];
ld ans;
void doit(int tp) {
    int suma = 0, sumb = 0;
    vector<pii> s;
    ru(i, 1, n) suma += ra[i] - la[i], s.push_back(mp(la[i], tp)), s.push_back(mp(ra[i], tp));
    ru(i, 1, m) sumb += rb[i] - lb[i], s.push_back(mp(lb[i], tp ^ 1)), s.push_back(mp(rb[i], tp ^ 1));
    //ru(i, 1, n) printf("%d %d\n", la[i], ra[i]);
    int cntb = 0;
    sort(s.begin(), s.end());
    int TP[2] = {0, 0};
    int l = 0;
    for (auto g: s) {
        int r = g.fi;
        if(tp == 0) {
        if(TP[tp]) {
            ld p = (ld)cntb / (sumb ? sumb : m);
            if(!suma) p *= 1.0 / n;
            else p *= (ld)(r - l) / suma;
            ans += (p - (1 - p - (TP[tp ^ 1] ? (ld)(r - l) / sumb : 0))) * (l + r) / 2;
        }
        if(TP[tp ^ 1]) {
            if(!sumb) cntb++;
            else cntb += r - l;
        }
        }
        else {
        if(TP[tp ^ 1]) {
            if(!sumb) cntb++;
            else cntb += r - l;
        }
        if(TP[tp]) {
            ld p = (ld)cntb / (sumb ? sumb : m);
            if(!suma) p *= 1.0 / n;
            else p *= (ld)(r - l) / suma;
            ans += (p - (1 - p - (TP[tp ^ 1] ? (ld)(r - l) / sumb : 0))) * (l + r) / 2;
        }
        }
        if(tp && TP[0] && TP[1] && l != r) {
            ans += (ld)(r - l) / 3 * (r - l) / suma * (r - l) / sumb;
        }
        TP[g.se] ^= 1;
        l = r;
    }
}
int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = read(), m = read();
    ru(i, 1, n) la[i] = read(), ra[i] = read();
    ru(i, 1, m) lb[i] = read(), rb[i] = read();
    doit(0);
    swap(n, m);
    ru(i, 1, max(n, m)) swap(la[i], lb[i]), swap(ra[i], rb[i]);
    doit(1);
    printf("%.11Lf\n", ans);
    return 0;
}

详细

Test #1:

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

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: 1ms
memory: 5816kb

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: 1ms
memory: 5772kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666666674

result:

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

Test #4:

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

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: 0ms
memory: 3844kb

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: 5764kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

-nan

result:

wrong output format Expected double, but "-nan" found