QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717624 | #5433. Absolute Difference | Hygebra | WA | 2ms | 12116kb | C++14 | 6.7kb | 2024-11-06 18:32:03 | 2024-11-06 18:32:03 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 500005;
const int INF = 2e9;
pair<int, int> a[N], b[N], x[N], y[N];
double w[N], g[N], f[N];
signed main() {
int n = 0, m = 0;
bool flagn = false, flagm = false;
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &a[i].first, &a[i].second);
if (a[i].first < a[i].second)
flagn = true;
}
for (int i = 1; i <= m; i++) {
scanf("%lld%lld", &b[i].first, &b[i].second);
if (b[i].first < b[i].second)
flagm = true;
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
//printf("114514----\n");
if (!flagn && !flagm) {
for (int i = 1; i <= m; i++)
w[i] = w[i - 1] + b[i].first;
double ans = 0;
for (int i = 1, j = 1; i <= n; i++) {
while (j <= m && b[j].first < a[i].first)
j++;
ans += (double)((double)a[i].first * (j - 1) - w[j - 1]) / ((double)n * m);
ans += (double)(w[m] - w[j - 1] - (double)a[i].first * (m - j + 1))/ ((double)n * m);
}
printf("%.11f\n", ans);
return 0;
}
//printf("191810\n");
if (flagn && !flagm) {
for (int i = 1; i <= max(n, m); i++)
swap(a[i], b[i]);
swap(n, m), swap(flagn, flagm);
}
if (!flagn && flagm) {
for (int i = 1; i <= m; i++) {
w[i] = w[i - 1];
if (b[i].first < b[i].second)
w[i] += (double)(b[i].second + b[i].first) * (b[i].second - b[i].first);
g[i] = g[i - 1] + (b[i].second - b[i].first);
}
double ans = 0;
for (int i = 1, j = 1; i <= n; i++) {
while (j <= m && b[j].second <= a[i].first)
j++;
if (j <= m && b[j].first < a[i].first) {
ans += ((double)2 * a[i].first * (j - 1) * g[j - 1] - w[j - 1]) / 2.0 / g[m] / n;
ans += (w[m] - w[j] - (double)2 * a[i].first * (m - j) * (g[m] - g[j])) / 2.0 / g[m] / n;
ans += ((double)2 * a[i].first - (a[i].first + b[j].first)) / 2.0 * ((double)(a[i].first - b[j].first) / g[m]) / n;
ans += ((double)a[i].first + b[j].second - 2 * a[i].first) / 2.0 * ((double)(b[j].second - a[i].first) / g[m]) / n;
} else {
ans += ((double)2 * a[i].first * (j - 1) * g[j - 1]- w[j - 1]) / 2.0 / g[m] / n;
ans += (w[m] - w[j - 1] - (double)2 * a[i].first * (m - j + 1) * (g[m] - g[j - 1])) / 2.0 / g[m] / n;
}
}
printf("%.11f\n", ans);
return 0;
}
int u = 1, v = 1, tn = 0, tm = 0;
x[0] = y[0] = make_pair(-INF,-INF);
while (u <= n || v <= m) {
if (u <= n && a[u].first == a[u].second) {
u++; continue;
}
if (v <= m && b[v].first == b[v].second) {
v++; continue;
}
if (u <= n && v > m)
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second), u++;
else if (u <= n && v <= m && a[u] <= b[v] && a[u].second <= b[v].first)
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second), u++;
else if (u <= n && v <= m && a[u] <= b[v] && a[u].second > b[v].first) {
if (a[u] == b[v]) {
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second);
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second);
u++, v++;
} else if (a[u].first == b[v].first) {
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second);
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), a[u].second);
b[v].first = a[u].second;
u++;
} else {
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), b[v].first);
a[u].first = b[v].first;
}
}
else if (v <= m && u > n)
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second), v++;
else if (v <= m && u <= n && b[v] <= a[u] && b[v].second <= a[u].first)
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second), v++;
else {
if (a[u] == b[v]) {
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), a[u].second);
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second);
u++, v++;
} else if (a[u].first == b[v].first) {
tn++, x[tn] = make_pair(max(x[tn - 1].second, a[u].first), b[v].second);
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), b[v].second);
a[u].first = b[v].second;
v++;
} else {
tm++, y[tm] = make_pair(max(y[tm - 1].second, b[v].first), a[u].first);
b[v].first = a[u].first;
}
}
// printf("%d %d %d %d\n", u, v, tn, tm);
}
for (int i = 1; i <= tm; i++) {
//if (y[i].first < y[i].second)
w[i] = w[i - 1] + (double)(y[i].first + y[i].second) * (y[i].second - y[i].first);
g[i] = g[i - 1] + (y[i].second - y[i].first);
}
for (int i = 1; i <= tn; i++) {
f[i] = f[i - 1] + (x[i].second - x[i].first);
}
//printf("-------\n");
double ans = 0;
for (int i = 1, j = 1; i <= tn; i++) {
while (j <= tm && y[j].first < x[i].first)
j++;
//cout << j << " ---------\n";
if (j <= tm && y[j].first == x[i].first && y[j] != x[i]) printf("Layn Ak IOI\n");
if (j <= tm && y[j] == x[i]) {
//cout << f[tn] << " " << g[tm] << " ---\n";
ans += (x[i].second - x[i].first) / 3.0 * (x[i].second - x[i].first) / f[tn] * (y[i].second - y[i].first) / g[tm];
ans += ((double)(x[i].second + x[i].first) * (j - 1) * g[j - 1] - w[j - 1]) / 2.0 * (x[i].second - x[i].first) / f[tn] / g[tm];
ans += (w[tm] - w[j] - (double)(x[i].second + x[i].first) * (tm - j) * (g[tm] - g[j])) / 2.0 * (x[i].second - x[i].first) / f[tn] / g[tm];
} else {
ans += ((double)(x[i].second + x[i].first) * (j - 1) * g[j] - w[j - 1]) / 2.0 * (x[i].second - x[i].first) / f[tn] / g[tm];
ans += (w[tm] - w[j - 1] - (double)(x[i].second + x[i].first) * (tm - j + 1) * (g[tm] - g[j - 1])) / 2.0 * (x[i].second - x[i].first) / f[tn] / g[tm];
}
}
printf("%.11f", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12068kb
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: 0ms
memory: 7964kb
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: 2ms
memory: 12116kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.66666662693
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 12060kb
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: 7972kb
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: 7972kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.50000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7972kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.00000000000
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 8052kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.00000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 12052kb
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:
5743755.56122355536
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '5743755.5612236', error = '854.0923613'