QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780798#8676. Three Kinds of Diceucup-team5217#WA 15ms45536kbC++233.8kb2024-11-25 13:18:212024-11-25 13:18:21

Judging History

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

  • [2024-11-25 13:18:21]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:45536kb
  • [2024-11-25 13:18:21]
  • 提交

answer

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

using namespace std;

const int N = 1e6 + 10;
int n, m;
int a[N], b[N];
int tot;
ldb cntx[N], cnty[N];
int lsh[N];
// int x[N], y[N];
struct vec{
    ldb x,y;
    vec(ldb a=0,ldb 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*(ldb a)const {
        return {x*a,y*a};
    }
    ldb operator*(const vec a)const {
        return x*a.x+y*a.y;
    }    
    ldb operator^(const vec a)const {
        return x*a.y-y*a.x;
    }  
    ldb len(){
        return sqrt(x*x+y*y);
    }
    ldb len2(){
        return (x*x+y*y);
    }
};

vec p[N];
ldb ans;

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

ldb solve1() {
    for (int i = 1; i <= tot; ++i) {
        p[i].x = cntx[i];
        p[i].y = cnty[i];
    }
    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 + 1 < q.size(); ++i) {
        if (q[i].x <= 0 && q[i + 1].x >= 0) {
            return q[i].y + (q[i + 1].y - q[i].y) * ((-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);
    int 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] = a[i] + 1;
        }
        for (int i = 1; i <= m; ++i) {
            lsh[++tot] = max(1, b[i] - 1);
            lsh[++tot] = b[i];
            lsh[++tot] = b[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] += lower_bound(b + 1, b + m + 1, lsh[i]) - b - 1;
            cnty[i] += 1.0 * (upper_bound(b + 1, b + m + 1, lsh[i]) - lower_bound(b + 1, b + m + 1, lsh[i])) / 2;
            cnty[i] /= m;
        }
        ans = solve1();
        // printf("%.9Lf ", solve1());
        for (int i = 1; i <= tot; ++i) cntx[i] = cnty[i] = 0;
    };
    ope();
    printf("%.9Lf ", ans);
    swap(n, m);
    swap(a, b);

    for (int i = 1; i <= n; ++i) a[i] = 1000000001 - a[i];
    for (int i = 1; i <= m; ++i) b[i] = 1000000001 - b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    // sort()
    ope();
    printf("%.9Lf\n", 1 - ans);
    puts("");
    // cerr << check1(0.3) << '\n';
    // return 0;
    // ldb l = 0, r = 1;
    // for (int i = 1; i <= 30; ++i) {
    //     ldb mid = (l + r) / 2;
    //     if (check1(mid)) r = mid;
    //     else l = mid;
    // }
    // printf("%.9Lf\n", l);

    //todo : swap(a, b)
    // ldb l = 0, r = 1;
    // for (int i = 1; i <= 30; ++i) {
    //     ldb mid = (l + r) / 2;
    //     if (check2(mid)) r = mid;
    //     else l = mid;
    // }
    // printf("%d")

    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 45344kb

input:

3 2 4 9
3 1 6 8

output:

0.291666667 0.750000000


result:

ok 2 numbers

Test #2:

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

input:

3 1 6 8
6 2 2 4 4 9 9

output:

0.291666667 0.750000000


result:

ok 2 numbers

Test #3:

score: -100
Wrong Answer
time: 15ms
memory: 45536kb

input:

1 1
1 2

output:

0.750000000 0.500000000


result:

wrong answer 2nd numbers differ - expected: '0.0000000', found: '0.5000000', error = '0.5000000'