QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385871#5433. Absolute Differencewsc2008WA 1ms8076kbC++141.7kb2024-04-11 09:19:152024-04-11 09:19:16

Judging History

你现在查看的是最新测评结果

  • [2024-04-11 09:19:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8076kb
  • [2024-04-11 09:19:15]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=4e5+9;
ll n,m,suma,sumb,tot;
struct Seg{
	ll l,r;
}a[N],b[N];
struct Node{
	ll p,t;
}c[N];
ld coefa(ll len){
	if(suma==0)return 1./n;
	return len*1./suma;
}
ld coefb(ll len){
	if(sumb==0)return 1./m;
	return len*1./sumb;
}
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	n=read(),m=read();
	rep(i,1,n)a[i].l=read(),a[i].r=read();
	rep(i,1,m)b[i].l=read(),b[i].r=read();
	rep(i,1,n)suma+=a[i].r-a[i].l;
	rep(i,1,m)sumb+=b[i].r-b[i].l;
	sort(a+1,a+n+1,[&](Seg a,Seg b){
		return a.l<b.l;
	});
	sort(b+1,b+m+1,[&](Seg a,Seg b){
		return a.l<b.l;
	});
	rep(i,1,n)c[++tot]=(Node){a[i].l,0},c[++tot]=(Node){a[i].r,0};
	rep(i,1,m)c[++tot]=(Node){b[i].l,1},c[++tot]=(Node){b[i].r,1};
	sort(c+1,c+tot+1,[&](Node a,Node b){
		return a.p<b.p;
	});
	ld ans=0,pa=0,sma=0,pb=0,smb=0;
	ll fa=0,fb=0;
	rep(i,1,tot-1){
		if(!c[i].t)fa^=1;
		else fb^=1;
		ll len=c[i+1].p-c[i].p;
		ld mid=(c[i].p+c[i+1].p)/2.;
		if(fa&&fb)ans+=1./3*len*coefa(len)*coefb(len);
		if(fa)ans+=(mid*pb-smb)*coefa(len);
		if(fb)ans+=(mid*pa-sma)*coefb(len);
		if(fa)pa+=coefa(len),sma+=mid*coefa(len);
		if(fb)pb+=coefb(len),smb+=mid*coefb(len);
	}
	cout<<fixed<<setprecision(12)<<ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7948kb

input:

1 1
0 1
0 1

output:

0.333333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 8020kb

input:

1 1
0 1
1 1

output:

0.500000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 8032kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666626930

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 8076kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 8012kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 8076kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7972kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999998.999999959138

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7884kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 8020kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

6717.117145739454

result:

ok found '6717.117145739', expected '6717.117145739', error '0.000000000'

Test #10:

score: -100
Wrong Answer
time: 1ms
memory: 8036kb

input:

1000 1000
-5010 -4999
-2128 -2113
-5798 -5765
705 713
-3956 -3938
-5308 -5307
6759 6772
-772 -770
-860 -859
2308 2323
-5500 -5500
5140 5177
-6747 -6733
7509 7511
8864 8870
-6382 -6374
1901 1904
-5763 -5760
3019 3027
2962 2963
-314 -301
-222 -203
-726 -724
-62 -58
-1203 -1195
-5216 -5215
-4298 -4292
...

output:

6807.054599900646

result:

wrong answer 1st numbers differ - expected: '6682.5811275', found: '6807.0545999', error = '0.0186266'