QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21294 | #2822. 不等式 | gsh# | WA | 765ms | 25968kb | C++20 | 1.2kb | 2022-03-04 14:42:50 | 2022-05-08 02:50:49 |
Judging History
answer
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,l,r) for(int i=l;i>=r;i--)
#define lowbit(x) x&-x
#define MAXN 1000001
int N,a[MAXN],b[MAXN],p[MAXN],q[MAXN];double x[MAXN],sa[MAXN],sb[MAXN];
int get(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
void upd(int x,double v1,double v2){for(int i=x;i<=N;i+=lowbit(i))sa[i]+=v1,sb[i]+=v2;}
double ask1(int x){double ans=0;for(int i=x;i;i-=lowbit(i))ans+=sa[i];return ans;}
double ask2(int x){double ans=0;for(int i=x;i;i-=lowbit(i))ans+=sb[i];return ans;}
int main()
{
N=get();For(i,1,N)a[i]=get();For(i,1,N)b[i]=get(),x[i]=-1.0*b[i]/a[i];
For(i,1,N)p[i]=i;sort(p+1,p+N+1,[&](int a,int b){return x[a]<x[b];});For(i,1,N)q[p[i]]=i;
double s=0;
For(i,1,N)
{
if(a[i]>0)upd(1,-a[i],-b[i]),upd(q[i],2*a[i],2*b[i]);else if(a[i]<0)upd(1,a[i],b[i]),upd(q[i],-2*a[i],-2*b[i]);else s+=b[i];
int l=1,r=N;while(l<r){int mid=l+r>>1;if(ask1(mid)>0)r=mid;else l=mid+1;}
double a=ask1(l),b=ask2(l);printf("%.10lf\n",a*x[p[l]]+b+s);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 14020kb
input:
1000 61238 60248 73732 -26564 -93007 4478 -39783 -29386 6714 -96099 58853 29344 88517 -7643 -16343 97123 82004 96690 -63916 13672 -72104 -93128 -33526 4108 -5475 -53323 57787 15891 -9523 -10161 -96799 -83119 77140 97223 -56595 -95821 24758 73652 58307 -22694 -62422 2448 59087 -47128 67302 -53844 -61...
output:
0.0000000000 21040.3674842418 46739.8011692087 118552.3871778961 134885.2909243390 138647.7562118980 181413.0968851807 262021.9724859419 332218.4892212414 448697.7365037040 526654.9827231457 604758.2670237435 622459.0320715895 625160.8650837715 633787.7989086842 654740.7191612910 679518.0803346169 7...
result:
ok 1000 numbers
Test #2:
score: -100
Wrong Answer
time: 765ms
memory: 25968kb
input:
500000 72535 50164 -41705 -27256 99923 -47337 -84129 -19076 -28224 47616 20591 30941 35900 -30965 1834 -33114 62440 56631 -45421 84047 77094 -86440 30282 -60892 44910 89786 -566 -87476 60388 13980 63363 91246 10736 59064 7550 30290 -68811 73956 90454 6060 76719 -58321 66048 -6321 -39195 24249 -20336...
output:
0.0000000000 60376.9402357483 66670.5308476202 164077.4140990289 182310.2016268008 183734.7840352933 249323.8172676764 322652.8750749311 323189.0759991496 351287.6426262754 410937.4178127046 460816.5299026132 493996.4337832985 550307.8996979108 578503.9449268015 601978.5788929482 638641.1839575807 6...
result:
wrong answer 156720th numbers differ - expected: '7845248160.4640989', found: '7845217104.4640989', error = '0.0000040'