QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21406#2822. 不等式qingyu_orz#WA 0ms11988kbC++201.5kb2022-03-04 20:05:592022-05-08 03:12:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 03:12:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11988kb
  • [2022-03-04 20:05:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct apple{
	int a,b;
	bool operator<(const apple &other)const{
		return 1ll*a*other.b>1ll*b*other.a;
	}
}e[500005];
int ss[500005];
long long sm[2000005];
double s2[2000005];
int A[500005],B[500005];
void add(int l,int r,int o,int x,int v){
	if(v==0)return;
	if(l==r){
		sm[o]+=v,s2[o]+=1.0*v*e[x].b/e[x].a;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)add(l,mid,o<<1,x,v);
	else add(mid+1,r,o<<1|1,x,v);
	sm[o]=sm[o<<1]+sm[o<<1|1];
	s2[o]=s2[o<<1]+s2[o<<1|1];
}
int query(int l,int r,int o,long long pm){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(pm<=sm[o<<1])return query(l,mid,o<<1,pm);
	return query(mid+1,r,o<<1|1,pm-sm[o<<1]);
}
double query2(int l,int r,int o,int x,double zz){
	if(l==r){
		return 0;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		double ans=s2[o<<1|1]-sm[o<<1|1]*zz;
		return ans+query2(l,mid,o<<1,x,zz);
	}
	double ans=sm[o<<1]*zz-s2[o<<1];
	return ans+query2(mid+1,r,o<<1|1,x,zz);
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&e[i].a,&e[i].b);
		if(e[i].a==0){
			ss[i]=abs(e[i].b);
		}
		if(e[i].a<0)e[i].a=-e[i].a,e[i].b=-e[i].b;
		A[i]=e[i].a,B[i]=e[i].b;
	}
	sort(e+1,e+n+1);
	map<pair<int,int>,int>mp;
	for(int i=1;i<=n;++i)mp[make_pair(e[i].a,e[i].b)]=i;
	long long he=0;
	long long gs=0;
	for(int i=1;i<=n;++i){
		he+=ss[i];
		gs+=A[i];
		int wz=mp[make_pair(A[i],B[i])];
		add(1,n,1,wz,A[i]);
		int df=query(1,n,1,(gs+1)/2);
		printf("%.10f\n",he+query2(1,n,1,df,1.0*e[df].b/e[df].a));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 11988kb

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
82310.6896327239
86210.4524605675
117511.8811272270
213287.6227488254
245465.2130592321
248846.3927016246
345182.5276914641
445820.7672003182
456415.4090659842
553014.9941294742
555508.8207016676
609095.4250540282
627287.5359509925
634829.7809888037
691329.7679062765
751826.7525189880
8...

result:

wrong answer 2nd numbers differ - expected: '21040.3674840', found: '82310.6896327', error = '2.9120367'