QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783522#8676. Three Kinds of Dicepengpeng_fudanWA 153ms19260kbC++232.9kb2024-11-26 10:23:022024-11-26 10:23:03

Judging History

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

  • [2024-11-26 10:23:03]
  • 评测
  • 测评结果:WA
  • 用时:153ms
  • 内存:19260kb
  • [2024-11-26 10:23:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
struct vec{
    ll x,y;
    vec operator +(vec a){return {x+a.x,y+a.y};}
    vec operator -(vec a){return {x-a.x,y-a.y};}
    ll operator *(vec a){return x*a.x+y*a.y;}
    ll operator ^(vec a){return x*a.y-y*a.x;}
};
vector<vec> build_convex(vector<vec> pot){
    sort(pot.begin(),pot.end(),[&](vec a,vec b){return a.x<b.x;;});
    int n=pot.size();
    int lo=0;
    vector<vec> res;
    for(int i=0;i<n;i++){
        while(lo>=2&&((res[lo-1]-res[lo-2])^(pot[i]-res[lo-1]))<=0)    lo--,res.pop_back();
        res.push_back(pot[i]),lo++;
    }
    return res;
}
using ld =long double;
void solve(void) {
    int n,m;
    vector<int> w[2];
    cin>>n;
    for(int i=0;i<n;i++){
        int num;cin>>num;w[0].push_back(num);
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int num;cin>>num;w[1].push_back(num);
    }
    sort(w[0].begin(),w[0].end());
    sort(w[1].begin(),w[1].end());
    int num=0;
    for(int i=0;i<n;i++){
        num+=lower_bound(w[1].begin(),w[1].end(),w[0][i])-w[1].begin();
        num-=m-(upper_bound(w[1].begin(),w[1].end(),w[0][i])-w[1].begin());
    }
    if(num<0)   {swap(n,m);swap(w[0],w[1]);}
    auto ope=[&](int t)->ld {
        vector<int> mpx;
        for(auto i:w[0])    {
            if(i)mpx.push_back(i);if(i+1)mpx.push_back(i+1);if(i-1)mpx.push_back(i-1); 
        }
        for(auto i:w[1])    {
            if(i)mpx.push_back(i);if(i+1)mpx.push_back(i+1);if(i-1)mpx.push_back(i-1); 
        }
        vector<vec> pot;
        sort(mpx.begin(),mpx.end());
        mpx.erase(unique(mpx.begin(),mpx.end()),mpx.end());
        for(auto x:mpx){
            ll dx=+(lower_bound(w[0].begin(),w[0].end(),x)-w[0].begin())-(n-(upper_bound(w[0].begin(),w[0].end(),x)-w[0].begin()));
            ll dy=2*(lower_bound(w[1].begin(),w[1].end(),x)-w[1].begin())+(upper_bound(w[1].begin(),w[1].end(),x)-lower_bound(w[1].begin(),w[1].end(),x));
            pot.push_back({dx,t*dy});
            // cerr<<x<<' '<<dx<<' '<<dy<<'\n';
            // if(dy<0)    cerr<<(m-(upper_bound(w[1].begin(),w[1].end(),x)-w[1].begin()))<<'\n';
        }
        vector<vec> convex=build_convex(pot);
        // for(auto [x,y]:convex)  cerr<<x<<' '<<y<<'\n';
        int sz=convex.size();
        for(int i=0;i<sz-1;i++){
            auto [x1,y1]=convex[i];
            auto [x2,y2]=convex[i+1];
            if(x1<=0&&x2>0){
                return ((ld)y1+(ld)(y2-y1)/(x2-x1)*(-x1))/(2*m);
            }
        }
    };
    cout<<setprecision(12);
    cout<<ope(1)<<' ';
    swap(n,m);
    swap(w[0],w[1]);
    // for(auto& i:w[0])   i=-i;    
    // for(auto& i:w[1])   i=-i;    
    cout<<-ope(-1)<<'\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int _ = 1;
    // cin >> _;
    while (_--) solve();

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4052kb

input:

3 2 4 9
3 1 6 8

output:

0.291666666667 0.75

result:

ok 2 numbers

Test #2:

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

input:

3 1 6 8
6 2 2 4 4 9 9

output:

0.291666666667 0.75

result:

ok 2 numbers

Test #3:

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

input:

1 1
1 2

output:

0.75 -0

result:

ok 2 numbers

Test #4:

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

input:

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

output:

0.5 0.5

result:

ok 2 numbers

Test #5:

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

input:

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

output:

0.25 0.75

result:

ok 2 numbers

Test #6:

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

input:

11 12 11 15 9 3 8 18 4 17 13 9
11 8 18 5 15 12 5 11 11 11 3 8

output:

0.473684210526 0.525

result:

ok 2 numbers

Test #7:

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

input:

20 17 18 29 37 5 15 5 9 37 34 12 38 26 29 2 40 23 20 4 12
23 22 2 24 33 6 19 15 31 1 18 30 11 40 13 2 19 5 39 37 22 9 31 26

output:

0.440503432494 0.554166666667

result:

ok 2 numbers

Test #8:

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

input:

40 52 22 29 52 44 3 69 45 40 73 66 51 2 21 20 51 49 34 72 64 69 68 56 4 6 39 29 18 43 6 56 15 22 31 25 78 59 58 40 66
46 52 24 40 12 56 7 4 29 12 26 45 39 27 47 55 45 17 74 28 12 75 77 77 73 41 21 20 23 55 13 58 21 43 11 22 2 67 18 49 56 15 26 25 35 20 61

output:

0.433971447112 0.565224358974

result:

ok 2 numbers

Test #9:

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

input:

76 54 80 5 41 10 124 87 45 67 42 118 33 128 118 21 40 41 3 18 69 131 113 121 106 99 72 108 85 101 108 72 27 13 45 133 137 4 62 30 111 71 39 31 120 79 91 30 58 43 6 60 65 83 83 42 83 26 108 20 133 24 8 125 138 100 21 103 81 45 102 76 44 118 109 18 67
81 4 15 26 65 110 48 126 39 128 82 1 43 134 18 69 ...

output:

0.421188630491 0.573711063373

result:

ok 2 numbers

Test #10:

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

input:

96 11 1 23 7 6 41 8 11 40 5 24 32 40 40 24 24 24 23 17 21 27 21 21 42 1 29 15 45 24 44 50 1 34 11 7 1 12 45 15 3 14 9 25 5 5 20 31 1 41 44 7 27 28 11 24 37 50 7 7 48 1 22 4 5 40 32 33 32 18 18 26 49 28 34 42 29 15 18 4 42 12 21 17 10 47 2 44 40 8 15 7 44 25 5 13 19
88 16 30 20 24 2 26 39 28 1 16 10 ...

output:

0.48185483871 0.518595041322

result:

ok 2 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

208 31 110 162 24 386 12 262 283 384 392 361 168 58 129 155 45 36 70 2 127 296 380 188 125 148 77 117 272 219 38 79 322 70 91 115 273 228 375 398 353 277 307 258 60 42 60 298 109 60 158 192 159 29 165 103 51 304 313 392 113 62 149 203 152 3 373 206 144 136 214 151 348 287 181 202 367 67 138 388 93 3...

output:

0.49558779909 0.504427083333

result:

ok 2 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 3880kb

input:

1170 1311 1924 962 906 1767 1811 1941 1956 1311 364 371 1825 1155 918 1625 1882 1082 198 889 924 1830 244 589 1639 296 1326 1663 379 1479 1369 729 1698 870 1845 217 888 754 858 966 1887 61 1801 1002 1185 1848 610 1914 1742 409 648 781 445 1217 96 1639 1681 1028 923 123 1234 909 569 747 1182 1538 368...

output:

0.485542699331 0.514105003008

result:

ok 2 numbers

Test #13:

score: 0
Accepted
time: 36ms
memory: 7012kb

input:

22713 21796 19194 13993 27763 16658 14855 3720 21919 4029 27311 21879 4981 25538 24982 5230 7339 4299 26976 30753 39183 38686 25483 3489 12855 28134 34477 25105 39953 31801 23937 31229 26076 32962 33965 6078 33306 15915 21622 3643 29726 2542 27764 4554 17811 17329 10576 26448 24416 30696 3230 3730 1...

output:

0.499529338332 0.500470603064

result:

ok 2 numbers

Test #14:

score: 0
Accepted
time: 10ms
memory: 8032kb

input:

100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0.75 -0

result:

ok 2 numbers

Test #15:

score: 0
Accepted
time: 14ms
memory: 11068kb

input:

1 1
100000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100...

output:

0.75 -0

result:

ok 2 numbers

Test #16:

score: 0
Accepted
time: 24ms
memory: 13380kb

input:

100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0.75 -0

result:

ok 2 numbers

Test #17:

score: 0
Accepted
time: 22ms
memory: 12448kb

input:

100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0.50000499995 0.499995

result:

ok 2 numbers

Test #18:

score: 0
Accepted
time: 25ms
memory: 13064kb

input:

100000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 10000...

output:

0.5 0.5

result:

ok 2 numbers

Test #19:

score: 0
Accepted
time: 153ms
memory: 18576kb

input:

100000 100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 9995...

output:

0.500000000025 0.499999999975

result:

ok 2 numbers

Test #20:

score: 0
Accepted
time: 153ms
memory: 18132kb

input:

100000 100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 9995...

output:

0.5 0.5

result:

ok 2 numbers

Test #21:

score: 0
Accepted
time: 37ms
memory: 19260kb

input:

99818 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

0.212675039006 0.787320894634

result:

ok 2 numbers

Test #22:

score: 0
Accepted
time: 39ms
memory: 18260kb

input:

99536 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

0.00938489032657 0.747631549773

result:

ok 2 numbers

Test #23:

score: 0
Accepted
time: 40ms
memory: 17948kb

input:

99536 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

0.00938489032657 0.747631549773

result:

ok 2 numbers

Test #24:

score: -100
Wrong Answer
time: 0ms
memory: 3868kb

input:

77 171374872 241639648 194650219 785923176 44879978 171374872 572364662 194650219 622176869 572364662 44879978 637973696 629927342 629927342 802671596 241639648 44879978 802671596 194650219 572364662 629927342 629927342 629927342 637973696 171374872 701867938 171374872 572364662 44879978 785923176 7...

output:

0.344774273346 0.645773433007

result:

wrong answer 1st numbers differ - expected: '0.3432282', found: '0.3447743', error = '0.0015461'