QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270980#5433. Absolute Differenceship2077WA 1ms12128kbC++142.8kb2023-12-01 19:21:152023-12-01 19:21:16

Judging History

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

  • [2023-12-01 19:21:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:12128kb
  • [2023-12-01 19:21:15]
  • 提交

answer

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long double ld;
constexpr int M=2e5+5;
int n,m,num,suma,sumb,f[M],g[M],lsh[M];
pair<int,int>a[M],b[M];
ld ans,len,sum,Lsh[M],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;
}
ld calc(ld x1,ld y1,ld x2,ld y2){
	return (y1-x1)*(y2-x2)*(x2+y2-y1-x1)*0.5;
}
ld Calc(ld len){return len*len*len/3.0;}
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;
	}
	printf("%.15Lf\n",ans);
}
void subtask2(){
	if (suma) swap(n,m),swap(a,b),swap(suma,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],
			 pre2[i]=pre2[i-1]+1;
	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]);
	printf("%.15Lf\n",ans/n/sumb);
}
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<=num;i++) Lsh[i]=(ld)lsh[i]/suma/sumb;
	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]);
	printf("%.15Lf\n",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: 12128kb

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: 8860kb

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: 12124kb

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: 12116kb

input:

1 1
-1000000000 0
0 1000000000

output:

499999999.256690687994706

result:

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