QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224723 | #5433. Absolute Difference | ZSH_ZSH# | WA | 1ms | 10224kb | C++14 | 1.5kb | 2023-10-23 11:19:54 | 2023-10-23 11:19:55 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;
typedef long double db;
db eps=1e-12;
const int N=2000010;
int n,m,sa[N],sb[N],cnt;
db a[N][2],b[N][2],dis[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
rep(i,1,n)
{
rep(j,0,1) cin>>a[i][j];
a[i][1]+=eps;
rep(j,0,1) dis[++cnt]=a[i][j];
}
rep(i,1,n)
{
rep(j,0,1) cin>>b[i][j];
b[i][1]+=eps;
rep(j,0,1) dis[++cnt]=b[i][j];
}
sort(dis+1,dis+cnt+1);
int sz=unique(dis+1,dis+cnt+1)-dis-1;
rep(i,1,n)
{
int l=lower_bound(dis+1,dis+sz+1,a[i][0])-dis;
int r=lower_bound(dis+1,dis+sz+1,a[i][1])-dis;
sa[l]++;
sa[r]--;
}
rep(i,1,m)
{
int l=lower_bound(dis+1,dis+sz+1,b[i][0])-dis;
int r=lower_bound(dis+1,dis+sz+1,b[i][1])-dis;
sb[l]++;
sb[r]--;
}
rep(i,1,sz) sa[i]+=sa[i-1],sb[i]+=sb[i-1];
db lena=0,lenb=0;
rep(i,1,sz-1)
{
db d=dis[i+1]-dis[i];
if (sa[i]) lena+=d;
if (sb[i]) lenb+=d;
}
db a0=0,a1=0,b0=0,b1=0,ans=0;
rep(i,1,sz-1)
{
db d=dis[i+1]-dis[i];
db pa=d/lena,pb=d/lenb;
db mid=(dis[i]+dis[i+1])/2;
if (sa[i])
{
ans+=pa*mid*b0;
ans-=pa*b1;
}
if (sb[i])
{
ans+=pb*mid*a0;
ans-=pb*a1;
}
if (sa[i]&&sb[i])
{
ans+=pa*pb*d/3;
}
if (sa[i])
{
a0+=pa;
a1+=pa*mid;
}
if (sb[i])
{
b0+=pb;
b1+=pb*mid;
}
}
printf("%.15Lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10224kb
input:
1 1 0 1 0 1
output:
0.333333333333667
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 10208kb
input:
1 1 0 1 1 1
output:
0.500000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 10160kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666666686069
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 10156kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 10052kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
0.000000000000000
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '0.0000000', error = '1.0000000'