QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#543233 | #8676. Three Kinds of Dice | qwerasdf | WA | 0ms | 3860kb | C++20 | 3.8kb | 2024-09-01 15:12:57 | 2024-09-01 15:12:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#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;
struct pt {
long double x, y;
bool operator == (pt const& t) const {
return x == t.x && y == t.y;
}
};
int orientation(pt a, pt b, pt c) {
long double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return 1; // clockwise
if (v > 0) return -1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; }
void convex_hull(vector<pt>& a, bool include_collinear = false) {
pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) {
return make_pair(a.y, a.x) < make_pair(b.y, b.x);
});
sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) {
int o = orientation(p0, a, b);
if (o == 0)
return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
< (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
return o < 0;
});
if (include_collinear) {
int i = (int)a.size()-1;
while (i >= 0 && collinear(p0, a[i], a.back())) i--;
reverse(a.begin()+i+1, a.end());
}
vector<pt> st;
for (int i = 0; i < (int)a.size(); i++) {
while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
st.pop_back();
st.push_back(a[i]);
}
if (include_collinear == false && st.size() == 2 && st[0] == st[1])
st.pop_back();
a = st;
}
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<pt> x(N);
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[i]={(small1+0.5*same1)/n,(small2+0.5*same2)/m};
}
vector<pt> orig=x;
convex_hull(x);
N=(int)x.size();
long double ans=1.0;
rep(i,0,N-1){
int j=i+1;
if(x[i].x>=0.5 || x[j].x<0.5)continue;
ans=x[i].y+((x[j].y-x[i].y)/(x[j].x-x[i].x)*(0.5-x[i].x));
}
cout<<fixed<<setprecision(9)<<ans<<' ';
x=orig;
for(auto &[u,v]:x){
swap(u,v);
u=1-u;
v=1-v;
}
reverse(all(x));
convex_hull(x);
N=(int)x.size();
ans=1.0;
rep(i,0,N-1){
int j=i+1;
if(x[i].x>=0.5 || x[j].x<0.5)continue;
ans=x[i].y+((x[j].y-x[i].y)/(x[j].x-x[i].x)*(0.5-x[i].x));
}
cout<<fixed<<setprecision(9)<<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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3860kb
input:
3 2 4 9 3 1 6 8
output:
0.333333333 0.666666667
result:
wrong answer 1st numbers differ - expected: '0.2916667', found: '0.3333333', error = '0.0416667'