QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604022 | #5433. Absolute Difference | SCUTkk | WA | 1ms | 3940kb | C++20 | 4.4kb | 2024-10-01 22:11:40 | 2024-10-01 22:11:41 |
Judging History
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'