QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431007 | #8676. Three Kinds of Dice | quack | WA | 0ms | 4100kb | C++14 | 2.1kb | 2024-06-04 20:03:13 | 2024-06-04 20:03:14 |
Judging History
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);
}
Details
Tip: Click on the bar to expand more detailed information
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'