QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#888160 | #9823. Mouse Trap | isWFnoya | WA | 38ms | 29752kb | C++26 | 2.2kb | 2025-02-07 23:02:52 | 2025-02-07 23:02:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll x[N],y[N];
double s[N],S[N];
double rs[N];
double sum[N],cnt[N];
int find(int l,int r,int X){
int num=x[l];
while(l<r){
int mid=l+r+1>>1;
if(x[mid]>=num) l=mid;
else r=mid-1;
}
return l;
}
double query(int l,int r){
double ans=s[r]-s[l-1];
double res=S[r]-S[l-1];
res*=(l-1)*2;
ans-=res;
return ans;
}
double query2(int l,int r){
double ans=rs[l]-rs[r+1];
double res=S[r]-S[l-1];
res*=(n-r)*2;
ans-=res;
return ans;
}
void __(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
x[i+n]=x[i];
y[i+n]=y[i];
}
// reverse(x+1,x+1+n);
// reverse(y+1,y+1+n);
for(int i=1;i<=n*2;i++){
S[i]=y[i];
s[i]=y[i]*i*2;
S[i]+=S[i-1];
s[i]+=s[i-1];
// cout<<s[i]<<" "<<S[i]<<endl;
}
for(int i=n*2;i>=1;i--){
rs[i]=y[i]*(n+1-i)*2;
rs[i]+=rs[i+1];
}
// for(int i=1;i<=n;i++)
for(int i=1;i<=n;i++){
int t=find(i,n+i-1,x[i]);
int sz=t-i;
// t-=i;
// cout<<sz<<endl;
ll val=(sz*(n-2)-sz*(sz-1));
// cout<<val<<endl;
cnt[i]-=val;
sum[i]-=n*(S[t]-S[i]);
sum[i]+=query(i+1,t);
sz=n-sz-1;
// cout<<sz<<endl;
val=(sz*(n-2)-sz*(sz-1));
cnt[i]+=val;
sum[i]+=n*(S[n+i-1]-S[t]);
sum[i]-=query2(t+1,n+i-1);
// cout<<n*(S[t]-S[i])<<" "<<n*(S[n]-S[t])<<" "<<query(i+1,t)<<" "<<query2(t+1,n)<<endl;
}
double fm=0;
for(int i=1;i<=n;i++){
fm+=(x[i]*y[i+1]-x[i+1]*y[i]);
}
double ans=0;
for(int i=1;i<=n;i++){
double res=x[i]*y[i];
res*=cnt[i];
ans+=res;
ans+=sum[i]*x[i];
// cout<<res<<" "<<sum[i]*x[i]<<endl;
// cout<<cnt[i]<<" "<<sum[i]<<endl;
// cout<<ans<<endl;
}
// cout<<ans<<endl;
ans/=fm;
printf("%.15f\n",-ans);
}
int main(){
int _=1;
// cin>>_;
while(_--){
__();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8016kb
input:
4 0 0 1 0 1 1 0 1
output:
2.000000000000000
result:
ok found '2.00000', expected '2.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 8136kb
input:
5 0 0 1 0 2 1 1 2 0 2
output:
3.666666666666667
result:
ok found '3.66667', expected '3.66667', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8136kb
input:
3 -3141592 -2718281 -3141593 -2718281 -3141592 -2718282
output:
1.000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 8012kb
input:
4 -10000000 -10000000 10000000 -10000000 10000000 10000000 -10000000 10000000
output:
2.000000000000000
result:
ok found '2.00000', expected '2.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7972kb
input:
6 -10000000 -10000000 0 -10000000 10000000 0 10000000 10000000 0 10000000 -10000000 0
output:
6.000000000000000
result:
ok found '6.00000', expected '6.00000', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 8012kb
input:
80 -56 -1 -55 -6 -54 -10 -53 -13 -51 -18 -50 -20 -47 -25 -45 -28 -42 -32 -38 -37 -37 -38 -32 -42 -28 -45 -25 -47 -20 -50 -18 -51 -13 -53 -10 -54 -6 -55 -1 -56 0 -56 5 -55 9 -54 12 -53 17 -51 19 -50 24 -47 27 -45 31 -42 36 -38 37 -37 41 -32 44 -28 46 -25 49 -20 50 -18 52 -13 53 -10 54 -6 55 -1 55 0 5...
output:
13022.364675557548253
result:
ok found '13022.36468', expected '13022.36468', error '0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 8396kb
input:
4336 -22883 -1 -22882 -43 -22881 -84 -22880 -124 -22879 -163 -22878 -201 -22877 -238 -22876 -274 -22875 -309 -22874 -343 -22873 -376 -22872 -408 -22871 -439 -22870 -469 -22869 -498 -22868 -526 -22867 -553 -22866 -579 -22865 -604 -22864 -628 -22863 -651 -22862 -673 -22861 -694 -22859 -735 -22858 -755...
output:
2071959690.152333021163940
result:
ok found '2071959690.15233', expected '2071959690.15233', error '0.00000'
Test #8:
score: -100
Wrong Answer
time: 38ms
memory: 29752kb
input:
199344 -7134251 -1 -7134250 -287 -7134249 -572 -7134248 -856 -7134247 -1139 -7134246 -1421 -7134245 -1702 -7134244 -1982 -7134243 -2261 -7134242 -2539 -7134241 -2816 -7134240 -3092 -7134239 -3367 -7134238 -3641 -7134237 -3914 -7134236 -4186 -7134235 -4457 -7134234 -4727 -7134233 -4996 -7134232 -5264...
output:
114443304684019.718750000000000
result:
wrong answer 1st numbers differ - expected: '201338821149252.00000', found: '114443304684019.71875', error = '0.43159'