QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173767 | #5433. Absolute Difference | aesthetic | WA | 1ms | 4004kb | C++20 | 5.3kb | 2023-09-10 01:50:48 | 2023-09-10 01:50:49 |
Judging History
answer
#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
#define int long long
#define dbg_loc() cerr << __PRETTY_FUNCTION__ << " : " << __LINE__ << "\n"
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p){
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T_container,typename T=typename enable_if<!is_same<T_container,string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v){
os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}';
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){
cerr << ' ' << H;
dbg_out(T...);
}
#define LOCAL
#define LOCAL
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
#define N 1000010
int n, m;
vector<pii> A, B, va, vb;
long double ans = 0;
long double count(vector<long double> &pref, int l, int r){
if(l>r) return 0.0;
long double c = pref[r];
if(l>0) c -= pref[l-1];
return c;
}
bool ptA = false, segA = false, ptB = false, segB = false;
// b >= a
long double integral2(long double a, long double b){
return (b/3.0 - a/3.0);
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
A.resize(n),B.resize(m);
for(int i = 0; i < n; i++){
cin>>A[i].f>>A[i].s;
if(A[i].f == A[i].s) ptA = true;
else segA = true;
}
for(int i=0;i<m;i++){
cin>>B[i].f>>B[i].s;
if(B[i].f == B[i].s) ptB = true;
else segB=true;
}
rep(i,0,n) if(!segA or A[i].f != A[i].s) va.pb(A[i]);
rep(i,0,m) if(!segB or B[i].f != B[i].s) vb.pb(B[i]);
n = sz(va), m=sz(vb);
vector<int> pos;
// tudo segmento
for(int i = 0; i < n; i++){
pos.pb(A[i].f), pos.pb(A[i].s);
}
for(int i = 0; i < m; i++){
pos.pb(B[i].f), pos.pb(B[i].s);
}
sort(all(pos)), pos.erase(unique(all(pos)),pos.end());
A = va, B = vb;
n=sz(A), m = sz(B);
vector<pair<int, int>> lixos[2];
for(int i = 0; i < n; i++){
if(A[i].f == A[i].s){
lixos[0].pb(A[i]);
continue;
}
int curr = A[i].f;
auto it = upper_bound(all(pos), curr);
int old = A[i].f;
while(it != pos.end() and (*it) <= A[i].s){
lixos[0].pb({old, *it});
old = *(it);
it++;
}
}
for(int i = 0; i < m; i++){
if(B[i].f == B[i].s){
lixos[1].pb(B[i]);
continue;
}
int curr = B[i].f;
auto it = upper_bound(all(pos), curr);
int old = B[i].f;
while(it != pos.end() and (*it) <= B[i].s){
lixos[1].pb({old, (*it)});
old = *(it);
it++;
}
}
A = lixos[0];
B= lixos[1];
va=A,vb=B;
n = sz(va), m = sz(vb);
long double tot1=0,tot2=0;
if(segA)rep(i,0,n) tot1 += (va[i].s-va[i].f);
else tot1=n;
if(segB)rep(i,0,m) tot2 += (vb[i].s-vb[i].f);
else tot2=m;
sort(all(va)), sort(all(vb));
vector<long double> pref, pref_prob;
for(int i = 0; i < m; i++){
long double prob = 1;
if(segB) prob = (vb[i].s - vb[i].f);
long double E = (vb[i].f + vb[i].s)/2.0;
pref.pb( (pref.empty()?0:pref.back()) + prob*E );
pref_prob.pb( (pref_prob.empty()?0:pref_prob.back()) + prob );
}
// dbg(segA, segB);
for(int i = 0; i < n; i++){
long double prob = 1.0;
if(segA) prob = (va[i].s - va[i].f);
long double E = (va[i].f + va[i].s)/2.0;
int j = lower_bound(all(vb), pii(va[i].s,-1000000001)) - vb.begin();
ans += prob*(count(pref, j, m-1) - count(pref_prob, j, m-1)*E)/tot1;
if(j>0){
// dbg(i,ans, prob, pref_prob, pref);
if(vb[j-1] == va[i]){
long double prob2 = 1;
if(segB) prob2 = (va[i].s-va[i].f);
ans += (long double)1.0*prob*(prob2)*integral2(va[i].f, va[i].s)/tot1;
}
else ans += (long double)1.0*prob*(count(pref_prob, j-1, j-1)*E - count(pref, j-1, j-1))/tot1;
if(j-2>=0)ans += (long double)1.0 * prob*(count(pref_prob, 0, j-2)*E - count(pref, 0, j-2))/tot1;
}
}
ans /= ( tot2);
cout<<setprecision(20)<<scientific;
cout<<(ans)<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3728kb
input:
1 1 0 1 0 1
output:
3.33333333333333333342e-01
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
1 1 0 1 1 1
output:
5.00000000000000000000e-01
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
6.66666666666666666686e+08
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
1 1 -1000000000 0 0 1000000000
output:
1.00000000000000000000e+09
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1.00000000000000000000e+09
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1.00000000050000000000e+09
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
9.99999999000000000466e+08
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2.00000000000000000000e+09
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 4004kb
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:
6.70988117482313429107e+03
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '6709.8811748', error = '0.0010772'