QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430933 | #5433. Absolute Difference | ucup-team859# | WA | 1ms | 4068kb | C++14 | 5.5kb | 2024-06-04 18:23:20 | 2024-06-04 18:23:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
string to_string(const string &s) {
return '"' + s + '"';
}
string to_string(bool b) {
return b ? "true" : "false";
}
template <typename A, typename B>
string to_string(const pair<A, B> &p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string(const T &v) {
string s = "{";
bool first = true;
for (const auto &it : v) {
if (!first)
s += ", ";
else
first = false;
s += to_string(it);
}
return s += "}";
}
void debug_out() {
cerr << endl;
}
template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
cerr << to_string(first) << " ";
debug_out(rest...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto startTime = high_resolution_clock::now();
int get_time() {
auto stopTime = chrono::high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(stopTime - startTime);
return duration.count(); // in ms
}
ld calc_exp(pair<int, int> a, pair<int, int> b, int ta, int tb) {
if (a.second > b.second) {
swap(a, b);
swap(ta, tb);
}
if (a == b) {
return (a.second - a.first) / 3.0 * (a.second - a.first) / ta;
}
if (a.second <= b.first) {
return (b.second - b.first) / 2.0 * (b.second - b.first) / tb - (a.second - a.first) / 2.0 * (a.second - a.first) / ta;
}
if (a.first >= b.first) {
return calc_exp(a, make_pair(b.first, a.first), ta, tb)
+ calc_exp(a, a, ta, tb)
+ calc_exp(a, make_pair(a.second, b.second), ta, tb);
}
return calc_exp(make_pair(a.first, b.first), b, ta, tb)
+ calc_exp(make_pair(b.first, a.second), make_pair(b.first, a.second), ta, tb)
+ calc_exp(make_pair(b.first, a.second), make_pair(a.second, b.second), ta, tb);
}
vector<pair<int, int>> remove_bad(vector<pair<int, int>> &v) {
vector<pair<int, int>> nv;
for (auto it : v) {
if (it.first != it.second)
nv.push_back(it);
}
return nv;
}
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n), b(m);
ld ta = 0, tb = 0;
for (auto &it : a) {
cin >> it.first >> it.second;
ta += it.second - it.first;
}
for (auto &it : b) {
cin >> it.first >> it.second;
tb += it.second - it.first;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (ta == 0) {
swap(a, b);
swap(ta, tb);
swap(n, m);
}
if (ta == 0 && tb == 0) {
ld sb = 0, pfb = 0;
for (auto it : b)
sb += it.first;
int j = 0;
long double ans = 0;
for (int i = 0; i < a.size(); ++i) {
while (j < m && b[j].first < a[i].first) {
sb -= b[j].first;
pfb += b[j].first;
++j;
}
ans += a[i].first * j - pfb;
ans += sb - a[i].first * (m - j);
}
cout << fixed << setprecision(18) << ans / (n * m) << "\n";
return;
}
if (tb == 0) {
ld sb = 0, pfb = 0;
for (auto it : b)
sb += it.first;
int j = 0;
long double ans = 0;
for (int i = 0; i < a.size(); ++i) {
ld exp = (a[i].second - a[i].first) / 2.0 * (a[i].second - a[i].first) / ta;
ld w = (a[i].second - a[i].first) / ta;
while (j < m && b[j].first < a[i].first) {
sb -= b[j].first;
pfb += b[j].first;
++j;
}
ans += w * (exp * j - pfb);
while (j < m && b[j].first < a[i].second) {
sb -= b[j].first;
pfb += b[j].first;
ans += (b[j].first - a[i].first) / 2.0 * (b[j].first - a[i].first) / ta;
ans += (a[i].second - b[j].first) / 2.0 * (a[i].second - b[j].first) / ta;
++j;
}
ans += w * (sb - exp * (m - j));
}
cout << fixed << setprecision(18) << ans / m << "\n";
return;
}
a = remove_bad(a);
b = remove_bad(b);
n = a.size();
m = b.size();
vector<pair<ld, ld>> sf(m), pf(m);
for (int i = m - 1; i >= 0; --i) {
sf[i].first = (b[i].second - b[i].first) / 2.0 * (b[i].second - b[i].first) / tb;
sf[i].second = (b[i].second - b[i].first) / tb;
if (i + 1 < m) {
sf[i].first += sf[i + 1].first;
sf[i].second += sf[i + 1].second;
}
}
for (int i = m - 1; i >= 0; --i) {
pf[i].first = (b[i].second - b[i].first) / 2.0 * (b[i].second - b[i].first) / tb;
if (i - 1 >= 0) {
pf[i].first += pf[i - 1].first;
pf[i].second += pf[i - 1].second;
}
}
int i = 0;
ld ans = 0;
for (auto it : a) {
while (i < b.size() && b[i].second <= it.first) {
++i;
}
int i2 = i;
while (i2 < b.size() && b[i2].first <= it.second) {
ans += calc_exp(it, b[i2], ta, tb);
++i2;
}
ld exp = (it.second - it.first) / 2.0 * (it.second - it.first) / ta;
ld w = (it.second - it.first) / ta;
if (i > 0) {
ans += w * (exp * pf[i - 1].second - pf[i - 1].first);
}
if (i2 < b.size()) {
ans += w * (-exp * sf[i2].second + sf[i2].first);
}
}
cout << fixed << setprecision(18) << ans << "\n";
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4068kb
input:
1 1 0 1 0 1
output:
0.333333333333333315
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
1 1 0 1 1 1
output:
0.500000000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666626930236816
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3856kb
input:
1 1 -1000000000 0 0 1000000000
output:
0.000000000000000000
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '0.0000000', error = '1.0000000'