QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74231 | #5433. Absolute Difference | XKError | WA | 6ms | 4164kb | C++14 | 2.8kb | 2023-01-31 10:17:37 | 2023-01-31 10:17:39 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 200005
#define db double
#define int long long
using namespace std;
int n, m;
struct node{
int l, r;
db prb;
node () {}
node (int x, int y, db z = 0) {
l = x, r = y, prb = z;
}
int len() {
return r - l;
}
db mid() {
return (l + r) / 2.0;
}
bool operator ==(const node x) {
return l == x.l && r == x.r;
}
};
db ans;
void solve(vector<node> &a, vector<node> &b, int l, int r) {
if (a.empty() || b.empty()) return;
if (a.size() == 1 && b.size() == 1) {
if (a[0] == b[0]) {
ans += a[0].len() * a[0].prb * b[0].prb / 3;
return;
}
if (a[0].len() == 0 && b[0].len() == 0) {
ans += abs(a[0].l - b[0].l) * a[0].prb * b[0].prb;
return;
}
if (a[0].len() == 0) {
ans += fabs(a[0].l - b[0].mid()) * a[0].prb * b[0].prb;
return;
}
if (b[0].len() == 0) {
ans += fabs(b[0].l - a[0].mid()) * a[0].prb * b[0].prb;
return;
}
}
int mid = (l + r) >> 1;
// cout<<mid<<" "<<a[0].l<<" "<<a[0].r<<" "<<b[0].l<<" "<<b[0].r<<endl;
vector<node> la, ra, lb, rb;
for (auto x : a) {
if (x.r <= mid) la.push_back(x);
else if (x.l >= mid) ra.push_back(x);
else {
auto s = node(x.l, mid, x.prb * (mid - x.l) / (x.r - x.l));
auto t = node(mid, x.r, x.prb * (x.r - mid) / (x.r - x.l));
la.push_back(s);
ra.push_back(t);
}
}
for (auto x : b) {
if (x.r <= mid) lb.push_back(x);
else if (x.l >= mid) rb.push_back(x);
else {
auto s = node(x.l, mid, x.prb * (mid - x.l) / (x.r - x.l));
auto t = node(mid, x.r, x.prb * (x.r - mid) / (x.r - x.l));
lb.push_back(s);
rb.push_back(t);
}
}
db s = 0, t = 0;
db sp = 0, tp = 0;
if (la.size() && rb.size()) {
for (auto x : la) s += x.mid() * x.prb, sp += x.prb;
for (auto x : rb) t += x.mid() * x.prb, tp += x.prb;
// cout<<"ED:"<<s<<" "<<t<<endl;
ans += t * sp - s * tp;
s = t = 0;
}
if (lb.size() && ra.size()) {
for (auto x : la) s += x.mid() * x.prb, sp += x.prb;
for (auto x : rb) t += x.mid() * x.prb, tp += x.prb;
// cout<<"ED:"<<s<<" "<<t<<endl;
ans += t * sp - s * tp;
// ans += t - s;
}
solve(la, lb, l, mid);
solve(ra, rb, mid, r);
}
vector<node> a, b;
signed main() {
scanf("%lld%lld", &n, &m);
int sa = 0, sb = 0;
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%lld%lld", &x, &y);
a.push_back(node(x, y));
sa += y - x;
}
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%lld%lld", &x, &y);
b.push_back(node(x, y));
sb += y - x;
}
if (sa == 0) for (auto &x : a) x.prb = 1.0 / n;
else for (auto &x : a) x.prb = x.len() * 1.0 / sa;
if (sb == 0) for (auto &x : b) x.prb = 1.0 / m;
else for (auto &x : b) x.prb = x.len() * 1.0 / sb;
solve(a, b, (int)-1e9, (int)1e9);
printf("%.12lf\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3708kb
input:
1 1 0 1 0 1
output:
0.333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 1 0 1 1 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 4ms
memory: 3632kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666626930
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.499999880791
result:
ok found '1000000000.499999881', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.000000000000
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.000000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 6ms
memory: 4164kb
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:
10513.818751537108
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '10513.8187515', error = '0.5652278'