QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#150740 | #5433. Absolute Difference | TadijaSebez | WA | 1ms | 4036kb | C++14 | 1.9kb | 2023-08-26 06:24:34 | 2023-08-26 06:24:35 |
Judging History
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;
if(tme!=0){
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: 3852kb
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: 3844kb
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: 4036kb
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'