QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173767#5433. Absolute DifferenceaestheticWA 1ms4004kbC++205.3kb2023-09-10 01:50:482023-09-10 01:50:49

Judging History

你现在查看的是最新测评结果

  • [2023-09-10 01:50:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4004kb
  • [2023-09-10 01:50:48]
  • 提交

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'