QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#150739#5433. Absolute DifferenceTadijaSebezWA 1ms3840kbC++141.8kb2023-08-26 06:20:262023-08-26 06:20:27

Judging History

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

  • [2023-08-26 06:20:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2023-08-26 06:20:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ldb double

vector<pair<int,int>> Read(int n){
	vector<pair<int,int>> ans;
	int sum=0;
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%i %i",&l,&r);
		sum+=r-l;
		ans.pb({l,r});
	}
	if(sum!=0){
		vector<pair<int,int>> tmp;
		for(auto p:ans){
			if(p.first!=p.second){
				tmp.push_back(p);
			}
		}
		ans=tmp;
	}
	sort(ans.begin(),ans.end());
	return ans;
}

ldb AddBoth(ldb x){
	return 2*x/3-x/2;
}
ldb sq(ldb x){
	return x*x;
}

ldb Solve(vector<pair<int,int>> a,vector<pair<int,int>> b){
	vector<array<int,3>> evs;
	int sumA=0,cntA=0;
	for(auto p:a){
		sumA+=p.second-p.first;
		cntA++;
		if(p.first!=p.second){
			evs.push_back({p.first,0,1});
			evs.push_back({p.second,1,1});
		}else{
			evs.push_back({p.first,2,1});
		}
	}
	int sumB=0,cntB=0;
	for(auto p:b){
		sumB+=p.second-p.first;
		cntB++;
		if(p.first!=p.second){
			evs.push_back({p.first,0,2});
			evs.push_back({p.second,1,2});
		}else{
			evs.push_back({p.first,2,2});
		}
	}
	sort(evs.begin(),evs.end());
	int active=0;
	int tmpA=0,tmpB=0;
	int last=-1;
	ldb ans=0,L=0;
	for(auto ev:evs){
		int tme=ev[0]-last;
		ldb integral=sq(ev[0])/2-sq(last)/2;
		if(active&1){
			tmpA+=tme;
			ans-=tme*L;
			ans+=integral*tmpB;
		}
		if(active&2){
			tmpB+=tme;
			L+=integral;
		}
		if(active==3){
			ans+=AddBoth(tme);
		}

		if(ev[1]==2){
			if(ev[2]==1){
				tmpA++;
				ans+=(ldb)ev[0]*tmpB;
				ans-=L;
			}else{
				tmpB++;
				L+=ev[0];
			}
		}

		last=ev[0];
		if(ev[1]!=2){
			active^=ev[2];
		}
	}
	if(sumA==0)ans/=cntA;
	else ans/=sumA;
	if(sumB==0)ans/=cntB;
	else ans/=sumB;
	return ans;
}
int main(){
	int n,m;
	scanf("%i %i",&n,&m);
	auto a=Read(n);
	auto b=Read(m);
	ldb ans=Solve(a,b)+Solve(b,a);
	printf("%.12f\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3756kb

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

input:

1 1
0 1
1 1

output:

0.500000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

0.000000000167

result:

wrong answer 1st numbers differ - expected: '666666666.6666666', found: '0.0000000', error = '1.0000000'