QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138591 | #5433. Absolute Difference | Kronos | WA | 3ms | 3856kb | C++20 | 7.7kb | 2023-08-12 00:31:36 | 2023-08-12 00:31:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
#define contPrint \
{ \
*this << "["; \
int f = 0; \
for (auto it : x) { \
*this << (f ? ", " : ""); \
*this << it; \
f = 1; \
} \
*this << "]"; \
return *this; \
}
~debug() { cerr << endl; }
template <class c>
debug& operator<<(c x) {
cerr << x;
return *this;
}
template <class c, class d>
debug& operator<<(pair<c, d> x) {
*this << "(" << x.first << ", " << x.second << ")";
return *this;
}
template <class c>
debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};
#define dbg(x) "[" << #x << ": " << x << "] "
#define Wa() \
cerr << "[LINE: " << __LINE__ << "] -> "; \
debug() <<
#define FASTIO \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<array<int, 3>> events;
vector<pair<int, int>> seg_alice(n);
for (auto& [x, y] : seg_alice) {
scanf("%d %d", &x, &y);
events.push_back({x, 0, 0});
events.push_back({y, 1, 0});
}
vector<pair<int, int>> seg_bob(m);
for (auto& [x, y] : seg_bob) {
scanf("%d %d", &x, &y);
events.push_back({x, 0, 1});
events.push_back({y, 1, 1});
}
sort(events.begin(), events.end());
vector<pair<int, int>> new_seg_alice;
{
bool alice_running = false;
int a_st = -1;
for (auto [x, y, z] : events) {
if (z == 0) {
if (y == 0) {
a_st = x;
alice_running = true;
} else if (y == 1) {
new_seg_alice.push_back({a_st, x});
alice_running = false;
}
} else {
if (alice_running) {
new_seg_alice.push_back({a_st, x});
a_st = x;
}
}
}
}
sort(new_seg_alice.begin(), new_seg_alice.end());
new_seg_alice.resize(unique(new_seg_alice.begin(), new_seg_alice.end()) - new_seg_alice.begin());
for (auto& [x, y, z] : events) {
z ^= 1;
}
sort(events.begin(), events.end());
vector<pair<int, int>> new_seg_bob;
{
bool alice_running = false;
int a_st = -1;
for (auto [x, y, z] : events) {
Wa() dbg(x) dbg(y) dbg(z);
if (z == 0) {
if (y == 0) {
a_st = x;
alice_running = true;
} else if (y == 1) {
new_seg_bob.push_back({a_st, x});
alice_running = false;
}
} else {
if (alice_running) {
new_seg_bob.push_back({a_st, x});
a_st = x;
}
}
Wa() dbg(a_st);
}
}
sort(new_seg_bob.begin(), new_seg_bob.end());
new_seg_bob.resize(unique(new_seg_bob.begin(), new_seg_bob.end()) - new_seg_bob.begin());
vector <pair <int, int>> notun_seg_alice, notun_seg_bob;
int new_n = new_seg_alice.size();
int new_m = new_seg_bob.size();
for (int i = 0; i < new_n; ++i) {
if (!notun_seg_alice.empty() and notun_seg_alice.back().second == new_seg_alice[i].first) {
notun_seg_alice.back().second = new_seg_alice[i].second;
} else {
notun_seg_alice.push_back(new_seg_alice[i]);
}
}
for (int i = 0; i < new_m; ++i) {
if (!notun_seg_bob.empty() and notun_seg_bob.back().second == new_seg_bob[i].first) {
notun_seg_bob.back().second = new_seg_bob[i].second;
} else {
notun_seg_bob.push_back(new_seg_bob[i]);
}
}
new_seg_alice = notun_seg_alice;
new_seg_bob = notun_seg_bob;
new_n = new_seg_alice.size();
new_m = new_seg_bob.size();
Wa() dbg(new_seg_alice) dbg(new_seg_bob);
map <pair <int, int>, int> mp_alice, mp_bob;
for (int i = 0; i < new_n; i++) {
mp_alice[new_seg_alice[i]]++;
}
for (int i = 0; i < new_m; i++) {
mp_bob[new_seg_bob[i]]++;
}
long double tot_n = 0, tot_m = 0;
vector <long double> sq_alice(new_n + 1), sq_bob(new_m + 1);
vector <long double> dif_alice(new_n + 1), dif_bob(new_m + 1);
vector <long double> eq_sum_alice(new_n + 1), eq_sum_bob(new_m + 1);
vector <long double> val_sum_alice(new_n + 1), val_sum_bob(new_m + 1);
for (int i = 0; i < new_n; ++i) {
auto [x, y] = new_seg_alice[i];
sq_alice[i] = 1.0 * y * y - 1.0 * x * x;
dif_alice[i] = y - x;
if (x == y) eq_sum_alice[i] = 1, val_sum_alice[i] = x;
tot_n += y - x;
}
for (int i = 0; i < new_m; ++i) {
auto [x, y] = new_seg_bob[i];
sq_bob[i] = 1.0 * y * y - 1.0 * x * x;
dif_bob[i] = y - x;
if (x == y) eq_sum_bob[i] = 1, val_sum_alice[i] = x;
tot_m += y - x;
}
for (int i = 1; i < new_n + 1; ++i) {
sq_alice[i] += sq_alice[i - 1];
dif_alice[i] += dif_alice[i - 1];
eq_sum_alice[i] += eq_sum_alice[i - 1];
val_sum_alice[i] += val_sum_alice[i - 1];
}
for (int i = 1; i < new_m + 1; ++i) {
sq_bob[i] += sq_bob[i - 1];
dif_bob[i] += dif_bob[i - 1];
eq_sum_bob[i] += eq_sum_bob[i - 1];
val_sum_bob[i] += val_sum_bob[i - 1];
}
long double sum = 0;
for (int i = 0; i < new_n; ++i) {
long long a, b;
a = new_seg_alice[i].first;
b = new_seg_alice[i].second;
auto id = lower_bound(new_seg_bob.begin(), new_seg_bob.end(), new_seg_alice[i]) - new_seg_bob.begin();
long double sq_g = (sq_bob[new_m] - (id ? sq_bob[id - 1] : 0)) / 2.0;
long double dif_g = (dif_bob[new_m] - (id ? dif_bob[id - 1] : 0)) / 2.0;
sum += sq_g * (b - a) - dif_g * (b + a) * (b - a);
long double sq_l = -(id ? sq_bob[id - 1] : 0) / 2.0;
long double dif_l = -(id ? dif_bob[id - 1] : 0) / 2.0;
sum += sq_l * (b - a) - dif_l * (b + a) * (b - a);
Wa() dbg(sq_g) dbg(sq_l) dbg(dif_g) dbg(dif_l);
if (mp_alice[new_seg_alice[i]] and mp_bob[new_seg_alice[i]]) {
sum += 1.0 * (b - a) * (b - a) * (b - a) / 3.0;
}
long double eq_sum_g = eq_sum_bob[new_m] - (id ? eq_sum_bob[id - 1] : 0);
long double val_sum_g = val_sum_bob[new_m] - (id ? val_sum_bob[id - 1] : 0);
if (eq_sum_g) sum -= val_sum_g * (b - a) - (1.0 * b * b - 1.0 * a * a) / 2.0 * eq_sum_g;
long double eq_sum_l = (id ? eq_sum_bob[id - 1] : 0);
long double val_sum_l = (id ? val_sum_bob[id - 1] : 0);
if (eq_sum_l) sum -= (1.0 * b * b - 1.0 * a * a) / 2.0 * eq_sum_l - val_sum_l * (b - a);
Wa() dbg(b - a) dbg(b * b - a * a) dbg(eq_sum_g) dbg(eq_sum_l);
if (a == b) {
long double llen = new_m - id;
sum += sq_g * llen - 1.0 * a * dif_g * 2.0;
llen = id;
sum += 1.0 * a * dif_l * 2.0 - sq_l * id;
}
}
Wa() dbg(sum);
if (tot_n) sum /= tot_n;
else sum /= new_n;
if (tot_m) sum /= tot_m;
else sum /= new_m;
printf("%.10Lf\n", sum);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3736kb
input:
1 1 0 1 0 1
output:
0.3333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
1 1 0 1 1 1
output:
0.5000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.6666666297
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.0000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3856kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.0000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 3736kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
-0.5000000003
result:
wrong answer 1st numbers differ - expected: '1000000000.5000000', found: '-0.5000000', error = '1.0000000'