QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783465#8676. Three Kinds of Diceucup-team5217WA 8ms30656kbC++233.6kb2024-11-26 10:00:562024-11-26 10:00:57

Judging History

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

  • [2024-11-26 10:00:57]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:30656kb
  • [2024-11-26 10:00:56]
  • 提交

answer

#include <bits/stdc++.h>
#define ld long double

using namespace std;
using ll =long long;
const int N = 1e6 + 10;
int n, m;
int a[N], b[N];
int tot;
ll cntx[N],cnty[N];
int lsh[N];
// int x[N], y[N];
struct vec{
    ll x,y;
    vec(ll a=0,ll b=0){x=a,y=b;}
    vec operator+(const vec a)const {
        return {x+a.x,y+a.y};
    }
    vec operator-(const vec a)const {
        return {x-a.x,y-a.y};
    }
    vec operator*(ll a)const {
        return {x*a,y*a};
    }
    ll operator*(const vec a)const {
        return x*a.x+y*a.y;
    }    
    ll operator^(const vec a)const {
        return x*a.y-y*a.x;
    }  
    ll len(){
        return sqrt(x*x+y*y);
    }
    ll len2(){
        return (x*x+y*y);
    }
};

vec p[N];
ld ans;

bool cmp(vec a, vec b) {
    return a.x < b.x;
}

ld solve1() {
    for (int i = 1; i <= tot; ++i) {
        p[i].x = cntx[i];
        p[i].y = cnty[i];
        // cerr << p[i].x << ' ' << p[i].y << ' ' << lsh[i] << '\n';
    }
    sort(p + 1, p + tot + 1, cmp);
    vector<vec> q;
    for (int i = 1; i <= tot; ++i) {
        while (q.size() >= 2 && (((p[i] - q[q.size() - 2]) ^ (q[q.size() - 1] - q[q.size() - 2])) >= 0)) q.pop_back();
        q.push_back(p[i]);
    }
    // for (int i = 0; i < q.size(); ++i) {
    //     cerr << q[i].x << ' ' << q[i].y << '\n';
    // }
    for (int i = 0; i + 1 < q.size(); ++i) {
        if (q[i].x <= 0 && q[i + 1].y >= 0) {
            return q[i].y + (ld)(q[i + 1].y - q[i].y) * ((ld)(-q[i].x) / (q[i + 1].x - q[i].x));
        }
    }
    return 0;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &b[i]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    long long cnt = 0;
    for (int i = 1; i <= m; ++i) {
        cnt += lower_bound(a + 1, a + n + 1, b[i]) - a - 1;
        cnt -= (n - (upper_bound(a + 1, a + n + 1, b[i]) - a) + 1);
    }
    if (cnt > 0) {
        swap(n, m);
        swap(a, b);
    }
    auto ope=[&](){
        // cerr << n << ' ' << m << '\n';
        tot = 0;    
        for (int i = 1; i <= n; ++i) {
            lsh[++tot] = max(1, a[i] - 1);
            lsh[++tot] = a[i];
            lsh[++tot] = min(1000000001, a[i] + 1);
        }
        for (int i = 1; i <= m; ++i) {
            lsh[++tot] = max(1, b[i] - 1);
            lsh[++tot] = b[i];
            lsh[++tot] = min(1000000001, a[i] + 1);
        }
        sort(lsh + 1, lsh + tot + 1);
        tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
        for (int i = 1; i <= tot; ++i) {
            cntx[i] += lower_bound(a + 1, a + n + 1, lsh[i]) - a - 1;
            cntx[i] -= (n - (upper_bound(a + 1, a + n + 1, lsh[i]) - a) + 1);
        }
        for (int i = 1; i <= tot; ++i) {
            cnty[i] += 2 * (lower_bound(b + 1, b + m + 1, lsh[i]) - b - 1);
            cnty[i] += (upper_bound(b + 1, b + m + 1, lsh[i]) - lower_bound(b + 1, b + m + 1, lsh[i]));
            // cnty[i] /= m;
        }
        ans = solve1();
        for (int i = 1; i <= tot; ++i) cntx[i] = cnty[i] = 0;
    };
    ope();
    printf("%.12Lf ", (ld)ans/m/2);
    // return 0;
    swap(n, m);
    swap(a, b);

    for (int i = 1; i <= n; ++i) a[i] = 1000000002 - a[i];
    for (int i = 1; i <= m; ++i) b[i] = 1000000002 - b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    // sort()
    ope();
    printf("%.12Lf\n", 1 - (ld)ans/m/2);

    return 0;
}

/*
6 1 1 6 6 8 8
3 2 4 9
*/
/*
*/
/*
4 9 3 7 5
 3 4 2 3
*/
/*
3 3 3 3
1 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2 4 9
3 1 6 8

output:

0.291666666667 0.750000000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 8ms
memory: 28368kb

input:

3 1 6 8
6 2 2 4 4 9 9

output:

0.291666666667 0.750000000000

result:

ok 2 numbers

Test #3:

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

input:

1 1
1 2

output:

0.750000000000 0.000000000000

result:

ok 2 numbers

Test #4:

score: 0
Accepted
time: 7ms
memory: 28464kb

input:

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

output:

0.500000000000 0.500000000000

result:

ok 2 numbers

Test #5:

score: 0
Accepted
time: 3ms
memory: 30512kb

input:

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

output:

0.250000000000 0.750000000000

result:

ok 2 numbers

Test #6:

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

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.333333333333 0.525000000000

result:

wrong answer 1st numbers differ - expected: '0.4736842', found: '0.3333333', error = '0.1403509'