QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543277#8676. Three Kinds of DiceqwerasdfRE 0ms3928kbC++203.0kb2024-09-01 15:33:432024-09-01 15:33:43

Judging History

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

  • [2024-09-01 15:33:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3928kb
  • [2024-09-01 15:33:43]
  • 提交

answer

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder; //https://github.com/atcoder/ac-library

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define bit(n, k) ((n >> k) & 1)
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> pii;

void test_case(int tt){
    int n,m; cin>>n;
    vector<int> a(n);
    rep(i,0,n)cin>>a[i];
    cin>>m;
    vector<int> b(m);
    rep(i,0,m)cin>>b[i];
    sort(all(a));
    sort(all(b));
    ll sum=0;
    rep(i,0,n){
        int small=upper_bound(all(b),a[i]-1)-lower_bound(all(b),1);
        int same=upper_bound(all(b),a[i])-lower_bound(all(b),a[i]);
        sum+=2*small+same;
    }
    if(sum<(ll)n*m){
        swap(a,b);
        swap(n,m);
    }
    vector<int> v;
    rep(i,0,n)v.push_back(a[i]);
    rep(i,0,m)v.push_back(b[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    vector<int> w;
    if(v[0]>1)w.push_back(v[0]-1);
    rep(i,0,(int)v.size()){
        if(!w.empty() && w.back()+1<v[i])w.push_back(w.back()+1);
        w.push_back(v[i]);
    }
    w.push_back(w.back()+1);
    int N=(int)w.size();
    vector<pair<long double,long double>> x;
    rep(i,0,N){
        int small1=upper_bound(all(a),w[i-1])-lower_bound(all(a),1);
        int same1=upper_bound(all(a),w[i])-lower_bound(all(a),w[i]);
        int small2=upper_bound(all(b),w[i-1])-lower_bound(all(b),1);
        int same2=upper_bound(all(b),w[i])-lower_bound(all(b),w[i]);
        x.emplace_back((small1+0.5*same1)/n,(small2+0.5*same2)/m);
    }
    vector<int> st;
    rep(i,0,N){
        while((int)st.size()>=2){
            int len=(int)st.size();
            auto [x1,y1]=x[st[len-2]];
            auto [x2,y2]=x[st[len-1]];
            auto [cx,cy]=x[i];
            if((cx-x1)*(y2-y1)<(x2-x1)*(cy-y1))break;
            st.pop_back();
        }
        st.push_back(i);
    }
    long double ans=1.0;
    rep(i,0,(int)st.size()-1){
        auto [x1,y1]=x[st[i]];
        auto [x2,y2]=x[st[i+1]];
        if(x1>=0.5 || x2<0.5)continue;
        ans=y1+(y2-y1)/(x2-x1)*(0.5-x1);
    }
    cout<<fixed;
    cout.precision(9);
    cout<<ans<<' ';
    for(auto &[u,v]:x){
        swap(u,v);
        u=1-u;
        v=1-v;
    }
    reverse(all(x));
    st.clear();
    rep(i,0,N){
        while((int)st.size()>=2){
            int len=(int)st.size();
            auto [x1,y1]=x[st[len-2]];
            auto [x2,y2]=x[st[len-1]];
            auto [cx,cy]=x[i];
            if((cx-x1)*(y2-y1)<(x2-x1)*(cy-y1))break;
            st.pop_back();
        }
        st.push_back(i);
    }
    ans=1.0;
    rep(i,0,N-1){
        auto [x1,y1]=x[st[i]];
        auto [x2,y2]=x[st[i+1]];
        if(x1>=0.5 || x2<0.5)continue;
        ans=y1+(y2-y1)/(x2-x1)*(0.5-x1);
    }
    cout<<1-ans<<'\n';
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    //cin>>t;
    rep(i, 1, t + 1)
    {
        test_case(i);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

input:

3 2 4 9
3 1 6 8

output:

0.291666667 0.750000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3 1 6 8
6 2 2 4 4 9 9

output:

0.291666667 0.750000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

1 1
1 2

output:

0.750000000 0.000000000

result:

ok 2 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

5 2 2 2 3 3
6 5 5 6 6 6 7

output:

0.500000000 0.500000000

result:

ok 2 numbers

Test #5:

score: -100
Runtime Error

input:

6 2 2 7 7 9 9
6 3 3 5 5 10 10

output:


result: