QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431007#8676. Three Kinds of DicequackWA 0ms4100kbC++142.1kb2024-06-04 20:03:132024-06-04 20:03:14

Judging History

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

  • [2024-06-04 20:03:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4100kb
  • [2024-06-04 20:03:13]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, m, tot, w[400010];
vector<int> a, b, c;
vector<pii> pt, st;
int query(const vector<int> &v, int x) {
    auto it1 = lower_bound(v.begin(), v.end(), x);
    auto it2 = upper_bound(v.begin(), v.end(), x);
    int ans1 = it1 - v.begin(), ans2 = it2 - it1;
    return ans1 * 2 + ans2;
}
bool check(pii u, pii v, pii w) {
    return 1ll * (w.second - v.second) * (v.first - u.first) <= 1ll * (v.second - u.second) * (w.first - v.first);
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; ++i) scanf("%d", &x), a.push_back(x), c.push_back(x);
    scanf("%d", &m);
    for (int i = 0, x; i < m; ++i) scanf("%d", &x), b.push_back(x), c.push_back(x);
    c.push_back(1);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    long long tot = 0;
    for (int x : a) tot += query(b, x);
    if (tot < 1ll * n * m) {
        swap(n, m);
        swap(a, b);
    }
    sort(c.begin(), c.end());
    auto last = unique(c.begin(), c.end());
    c.erase(last, c.end());
    c.push_back(1e9 + 2);
    for (int i = 0; i < c.size() - 1; ++i) {
        pt.push_back(pii(query(a, c[i]), query(b, c[i])));
        if (c[i] + 1 < c[i+1])
            pt.push_back(pii(query(a, (c[i] + c[i+1]) / 2), query(b, (c[i] + c[i+1]) / 2)));
    }
    sort(pt.begin(), pt.end());
    for (pii p : pt) {
        while(st.size() > 1 && check(st[st.size()-2], st[st.size()-1], p)) st.pop_back();
        st.push_back(p);
    }
    double ans1, ans2;
    int k = lower_bound(st.begin(), st.end(), pii(n, 0)) - st.begin();
    if (st[k].first == n) ans1 = 0.5;
    else ans1 = (1.0 * (st[k].second - st[k-1].second) / (st[k].first - st[k-1].first) * (n - st[k-1].first) + st[k-1].second) / 2 / m;
    k = lower_bound(st.begin(), st.end(), pii(0, m), [](pii x, pii y){return x.second == y.second ? x.first < y.first : x.second < y.second;}) - st.begin();
    if (st[k].second == m) ans2 = 0.5;
    else ans2 = (1.0 * (st[k].first - st[k-1].first) / (st[k].second - st[k-1].second) * (m - st[k-1].second) + st[k-1].first) / 2 / n;
    printf("%lf %lf\n", ans1, ans2);
}

详细

Test #1:

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

input:

3 2 4 9
3 1 6 8

output:

0.291667 0.750000

result:

ok 2 numbers

Test #2:

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

input:

3 1 6 8
6 2 2 4 4 9 9

output:

0.291667 0.750000

result:

ok 2 numbers

Test #3:

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

input:

1 1
1 2

output:

0.750000 0.500000

result:

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