QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73966 | #5433. Absolute Difference | nweeks | WA | 2ms | 3648kb | C++17 | 4.4kb | 2023-01-29 19:53:33 | 2023-01-29 19:53:36 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct Intervalle {
int l, r;
bool operator<(Intervalle other) const { return l < other.l; }
};
double sq(int x) { return x * x; }
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int nAlice, nBob;
cin >> nAlice >> nBob;
vector<Intervalle> alice(nAlice), bob(nBob);
for (auto &[l, r] : alice) {
cin >> l >> r;
}
for (auto &[l, r] : bob) {
cin >> l >> r;
}
int sumAlice = 0, sumBob = 0;
for (auto [l, r] : alice)
sumAlice += r - l;
for (auto [l, r] : bob)
sumBob += r - l;
sort(alice.begin(), alice.end());
sort(bob.begin(), bob.end());
if (!sumBob) {
swap(sumBob, sumAlice);
swap(alice, bob);
swap(nAlice, nBob);
}
dbg(sumBob, sumAlice);
if (!sumBob and !sumAlice) {
int sol = 0;
int bobR = 0;
for (auto [l, r] : bob)
bobR += l;
int bobL = 0;
int curBob = 0;
for (auto [l, r] : alice) {
while (curBob < nBob and bob[curBob].l < l) {
bobL += bob[curBob].l;
bobR -= bob[curBob++].l;
}
sol += l * curBob - l * (nBob - curBob) + bobR - bobL;
}
cout << setprecision(15) << fixed << sol / (double)nBob / nAlice << endl;
return 0;
}
if (!sumAlice) {
double sol = 0;
double intR = 0, probR = 0, probL = 0, intL = 0;
for (auto [l, r] : bob) {
intR += (sq(r) - sq(l)) / 2;
probR += r - l;
}
int cur = 0;
for (auto [l, r] : alice) {
while (cur < nBob and bob[cur].l < l) {
if (bob[cur].l == bob[cur].r) {
++cur;
continue;
}
int nxtR = min(bob[cur].r, l);
probL += nxtR - bob[cur].l;
probR -= nxtR - bob[cur].l;
intL += (sq(nxtR) - sq(bob[cur].l)) / 2;
intR -= (sq(nxtR) - sq(bob[cur].l)) / 2;
bob[cur].l = nxtR;
}
sol += (probL - probR) * l + intR - intL;
}
cout << setprecision(15) << fixed << sol / sumBob / nAlice << endl;
return 0;
}
double probL = 0, intL = 0, probR = 0, intR = 0;
double sol = 0;
int posAlice = 0, posBob = 0;
auto applyAlice = [&](int l, int r) {
sol += probR * (sq(r) - sq(l)) / 2;
sol -= (r - l) * intR;
probL += r - l;
probL += r - l;
intL += (sq(r) - sq(l)) / 2;
};
auto applyBob = [&](int l, int r) {
sol += probL * (sq(r) - sq(l)) / 2;
sol -= (r - l) * intL;
probR += r - l;
intR += (sq(r) - sq(l)) / 2;
};
while (posAlice < nAlice or posBob < nBob) {
if (posAlice < nAlice and alice[posAlice].l == alice[posAlice].r) {
++posAlice;
continue;
}
if (posBob < nBob and bob[posBob].l == bob[posBob].r) {
++posBob;
continue;
}
dbg(posAlice, posBob);
if (posAlice == nAlice) {
auto [l, r] = bob[posBob];
applyBob(l, r);
++posBob;
} else if (posBob == nBob) {
auto [l, r] = alice[posAlice];
applyAlice(l, r);
++posAlice;
} else if (alice[posAlice].l < bob[posBob].l) {
double l = alice[posAlice].l;
double r = min(alice[posAlice].r, bob[posBob].l);
applyAlice(l, r);
alice[posAlice].l = r;
} else if (bob[posBob].l < alice[posAlice].l) {
double l = bob[posBob].l;
double r = min(alice[posAlice].l, bob[posBob].r);
applyBob(l, r);
bob[posBob].l = r;
} else {
auto &[la, ra] = alice[posAlice];
auto &[lb, rb] = bob[posBob];
dbg(la, ra, rb);
double l = la;
double r = min(ra, rb);
sol += 1 / 3. * (r - l) * (r - l) * (r - l);
intL += (sq(r) - sq(l)) / 2;
intR += (sq(r) - sq(l)) / 2;
probL += r - l;
probR += r - l;
la = lb = r;
}
}
dbg(sol);
cout << setprecision(15) << fixed << sol / sumAlice / sumBob << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3520kb
input:
1 1 0 1 0 1
output:
0.333333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1 0 1 1 1
output:
0.500000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666626930237
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3644kb
input:
1 1 -1000000000 0 0 1000000000
output:
1500000000.000000238418579
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '1500000000.0000002', error = '0.5000000'