QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139731 | #5433. Absolute Difference | xcyle# | WA | 1ms | 3712kb | C++20 | 3.2kb | 2023-08-14 12:54:01 | 2023-08-14 12:54:02 |
Judging History
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); p = p - (1 - p - ((TP[tp ^ 1] && l != r) ? (ld)(r - l) / sumb : 0));
if(!suma) p *= 1.0 / n;
else p *= (ld)(r - l) / suma;
ans += p * (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); p = p - (1 - p - ((TP[tp ^ 1] && l != r) ? (ld)(r - l) / sumb : 0));
if(!suma) p *= 1.0 / n;
else p *= (ld)(r - l) / suma;
ans += p * (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: 0
Wrong Answer
time: 1ms
memory: 3712kb
input:
1 1 0 1 0 1
output:
1.33333333333
result:
wrong answer 1st numbers differ - expected: '0.3333333', found: '1.3333333', error = '1.0000000'