QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780798 | #8676. Three Kinds of Dice | ucup-team5217# | WA | 15ms | 45536kb | C++23 | 3.8kb | 2024-11-25 13:18:21 | 2024-11-25 13:18:21 |
Judging History
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'