QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270999#5433. Absolute Differenceship2077WA 0ms9776kbC++142.9kb2023-12-01 19:57:202023-12-01 19:57:20

Judging History

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

  • [2023-12-01 19:57:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9776kb
  • [2023-12-01 19:57:20]
  • 提交

answer

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long double f128;
constexpr int M=4e5+5;
int n,m,num,suma,sumb,f[M],g[M],lsh[M];
pair<int,int>a[M],b[M];long long pr[16];
f128 ans,len,sum,coef,pre1[M],pre2[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
f128 Calc(f128 len){return len*len*len/3.0;}
void print(f128 x){
	pr[0]=floor(x);x-=pr[0];
	for (int i=1;i<=15;i++)
		x*=10,pr[i]=floor(x),x-=pr[i];
	printf("%lld.",pr[0]);
	for (int i=1;i<=15;i++)
		printf("%lld",pr[i]);
}
void subtask1(){ len=n*m;
	for (int i=1;i<=m;i++) sum+=b[i].x/len;
	for (int i=1,j=0;i<=n;i++){
		while (j<m&&b[j+1].x<=a[i].x)
			sum-=b[++j].x*2/len;
		ans+=a[i].x*(j*2-m)/len+sum;
	}
	print(ans);
}
void subtask2(){
	if (suma) swap(n,m),swap(a,b),swap(suma,sumb); coef=(f128)1/n/sumb;
	for (int i=1;i<=n;i++) lsh[++num]=a[i].x;
	for (int i=1;i<=m;i++) lsh[++num]=b[i].x,lsh[++num]=b[i].y;
	sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
	for (int i=1;i<=n;i++) f[lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh]=1;
	for (int i=1;i<=m;i++)
		g[lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh]++,
		g[lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh]--;
	for (int i=1;i<=num;i++) g[i]+=g[i-1];
	for (int i=1;i<=num;i++)
		if (!f[i]) pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
		else pre1[i]=pre1[i-1]+lsh[i]*coef,
			 pre2[i]=pre2[i-1]+coef;
	for (int i=1;i<=num;i++)
		if (g[i])
			ans+=(lsh[i+1]*lsh[i+1]-lsh[i]*lsh[i])*(pre2[i]-pre2[num]*0.5)
			  +(-pre1[i]+(pre1[num]-pre1[i]))*(lsh[i+1]-lsh[i]);
	print(ans);
}
void subtask3(){
	for (int i=1;i<=n;i++) lsh[++num]=a[i].x,lsh[++num]=a[i].y;
	for (int i=1;i<=m;i++) lsh[++num]=b[i].x,lsh[++num]=b[i].y;
	sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
	for (int i=1;i<=n;i++)
		f[lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh]++,
		f[lower_bound(lsh+1,lsh+num+1,a[i].y)-lsh]--;
	for (int i=1;i<=m;i++)
		g[lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh]++,
		g[lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh]--;
	for (int i=1;i<=num;i++) f[i]+=f[i-1],g[i]+=g[i-1];
	for (int i=1;i<=num;i++)
		if (!g[i]) pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
		else pre1[i]=pre1[i-1]+(lsh[i]-lsh[i+1])*(lsh[i]+lsh[i+1]),
			 pre2[i]=pre2[i-1]+(lsh[i+1]-lsh[i]);
	for (int i=1;i<=num;i++) if (f[i])
		ans+=(-pre1[num]+pre1[i]+pre1[i-1]+(-pre2[num]+pre2[i]+pre2[i-1])*(lsh[i]+lsh[i+1]))*(lsh[i+1]-lsh[i])*0.5;
	for (int i=1;i<=num;i++) if (f[i]&&g[i]) ans+=Calc(lsh[i+1]-lsh[i]);
	print(ans/suma/sumb);
}
int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]={read(),read()},suma+=a[i].y-a[i].x;
	for (int i=1;i<=m;i++) b[i]={read(),read()},sumb+=b[i].y-b[i].x;
	sort(a+1,a+n+1);sort(b+1,b+m+1);
	if (!suma&&!sumb) return subtask1(),0;
	if (!suma||!sumb) return subtask2(),0;
	return subtask3(),0;
}

詳細信息

Test #1:

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

input:

1 1
0 1
0 1

output:

0.333333333333333

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 9776kb

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: 0ms
memory: 3576kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686069

result:

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

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3548kb

input:

1 1
-1000000000 0
0 1000000000

output:

499999999.256690687994705

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '499999999.2566907', error = '0.5000000'