QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#543277 | #8676. Three Kinds of Dice | qwerasdf | RE | 0ms | 3928kb | C++20 | 3.0kb | 2024-09-01 15:33:43 | 2024-09-01 15:33:43 |
Judging History
answer
//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder; //https://github.com/atcoder/ac-library
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define bit(n, k) ((n >> k) & 1)
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> pii;
void test_case(int tt){
int n,m; cin>>n;
vector<int> a(n);
rep(i,0,n)cin>>a[i];
cin>>m;
vector<int> b(m);
rep(i,0,m)cin>>b[i];
sort(all(a));
sort(all(b));
ll sum=0;
rep(i,0,n){
int small=upper_bound(all(b),a[i]-1)-lower_bound(all(b),1);
int same=upper_bound(all(b),a[i])-lower_bound(all(b),a[i]);
sum+=2*small+same;
}
if(sum<(ll)n*m){
swap(a,b);
swap(n,m);
}
vector<int> v;
rep(i,0,n)v.push_back(a[i]);
rep(i,0,m)v.push_back(b[i]);
sort(all(v));
v.erase(unique(all(v)),v.end());
vector<int> w;
if(v[0]>1)w.push_back(v[0]-1);
rep(i,0,(int)v.size()){
if(!w.empty() && w.back()+1<v[i])w.push_back(w.back()+1);
w.push_back(v[i]);
}
w.push_back(w.back()+1);
int N=(int)w.size();
vector<pair<long double,long double>> x;
rep(i,0,N){
int small1=upper_bound(all(a),w[i-1])-lower_bound(all(a),1);
int same1=upper_bound(all(a),w[i])-lower_bound(all(a),w[i]);
int small2=upper_bound(all(b),w[i-1])-lower_bound(all(b),1);
int same2=upper_bound(all(b),w[i])-lower_bound(all(b),w[i]);
x.emplace_back((small1+0.5*same1)/n,(small2+0.5*same2)/m);
}
vector<int> st;
rep(i,0,N){
while((int)st.size()>=2){
int len=(int)st.size();
auto [x1,y1]=x[st[len-2]];
auto [x2,y2]=x[st[len-1]];
auto [cx,cy]=x[i];
if((cx-x1)*(y2-y1)<(x2-x1)*(cy-y1))break;
st.pop_back();
}
st.push_back(i);
}
long double ans=1.0;
rep(i,0,(int)st.size()-1){
auto [x1,y1]=x[st[i]];
auto [x2,y2]=x[st[i+1]];
if(x1>=0.5 || x2<0.5)continue;
ans=y1+(y2-y1)/(x2-x1)*(0.5-x1);
}
cout<<fixed;
cout.precision(9);
cout<<ans<<' ';
for(auto &[u,v]:x){
swap(u,v);
u=1-u;
v=1-v;
}
reverse(all(x));
st.clear();
rep(i,0,N){
while((int)st.size()>=2){
int len=(int)st.size();
auto [x1,y1]=x[st[len-2]];
auto [x2,y2]=x[st[len-1]];
auto [cx,cy]=x[i];
if((cx-x1)*(y2-y1)<(x2-x1)*(cy-y1))break;
st.pop_back();
}
st.push_back(i);
}
ans=1.0;
rep(i,0,N-1){
auto [x1,y1]=x[st[i]];
auto [x2,y2]=x[st[i+1]];
if(x1>=0.5 || x2<0.5)continue;
ans=y1+(y2-y1)/(x2-x1)*(0.5-x1);
}
cout<<1-ans<<'\n';
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin>>t;
rep(i, 1, t + 1)
{
test_case(i);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
3 2 4 9 3 1 6 8
output:
0.291666667 0.750000000
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 1 6 8 6 2 2 4 4 9 9
output:
0.291666667 0.750000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 1 1 2
output:
0.750000000 0.000000000
result:
ok 2 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
5 2 2 2 3 3 6 5 5 6 6 6 7
output:
0.500000000 0.500000000
result:
ok 2 numbers
Test #5:
score: -100
Runtime Error
input:
6 2 2 7 7 9 9 6 3 3 5 5 10 10