QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783465 | #8676. Three Kinds of Dice | ucup-team5217 | WA | 8ms | 30656kb | C++23 | 3.6kb | 2024-11-26 10:00:56 | 2024-11-26 10:00:57 |
Judging History
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'