萌新求助
  • 板块CF626G Raffles
  • 楼主eexyz
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/4/25 13:31
  • 上次更新2023/11/5 00:09:00
查看原帖
萌新求助
126321
eexyz楼主2021/4/25 13:31

wa on test3

错误信息:wrong answer 53001st numbers differ - expected: '612912.1174680', found: '612912.7908075', error = '0.0000011'

不知道是精度挂了还是真的写错了。求大佬救命!!

#include<bits/stdc++.h>
using namespace std;
#define db long double
#define N 500005
#define int long long
db o=1;
struct ee{
	int pos;db val;
	bool operator == (ee aa) const {
		return pos==aa.pos&&val==aa.val;
	}
	bool operator <  (ee aa) const {
		return val<aa.val;
	}
}tmp,u;
ee mk(int a,db b){tmp.pos=a;tmp.val=b;return tmp;}
struct PQ{
	priority_queue<ee>f1,f2;
	void del(ee x){f2.push(x);}
	void push(ee x){f1.push(x);}
	void pop(){f1.pop();}
	ee top(){
		while(f2.size()&&f1.top()==f2.top())
			f1.pop(),f2.pop();
		return f1.top();
	}
	int size(){
		return f1.size()-f2.size();
	}
}g1;
struct PQ_{
	priority_queue<ee>f1,f2;
	void del(ee x){x.val=-x.val;f2.push(x);}
	void push(ee x){x.val=-x.val;f1.push(x);}
	void pop(){f1.pop();}
	ee top(){
		while(f2.size()&&f1.top()==f2.top())
			f1.pop(),f2.pop();
		ee ret=f1.top();
		ret.val=-ret.val;
		return ret;
	}
	int size(){
		return f1.size()-f2.size();
	}
}g2;
int i,tp,n,hs[N],l[N],t,q,p[N];
db ans;
void upd(){
	int i;
	while(t&&g1.size()){
		--t;
		u=g1.top();g1.pop();
		ans+=u.val;i=u.pos;
		g2.push(u);
		if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
		++hs[i];
		if(hs[i]<l[i])
			g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1)))); 
	}
	while(g1.size()&&g2.top()<g1.top()){
		u=g2.top();g2.pop();
		ans-=u.val;i=u.pos;
		g1.push(u);
		if(hs[i]!=l[i])g1.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i]+1)*(l[i]+hs[i]))));
		--hs[i];
		if(hs[i])
			g2.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
		u=g1.top();g1.pop();
		ans+=u.val;i=u.pos;
		g2.push(u);
		if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
		++hs[i];
		if(hs[i]<l[i])
			g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1)))); 
	}
}
signed main(){
	cin>>n>>t>>q;
	for(i=1;i<=n;++i)cin>>p[i];
	for(i=1;i<=n;++i)cin>>l[i],g1.push(mk(i,o*p[i]/(l[i]+1)));
	while(t&&g1.size()){
		--t;
		u=g1.top();g1.pop();
		ans+=u.val;i=u.pos;
		g2.push(u);
		if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
		++hs[i];
		if(hs[i]<l[i])
			g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
	}
	while(q--){
		cin>>tp>>i;
		cout<<tp<<" "<<i<<"\n";
		if(tp==1){
			ans-=o*p[i]*hs[i]/(hs[i]+l[i]);
			ans+=o*p[i]*hs[i]/(hs[i]+l[i]+1);
			if(hs[i]!=l[i])g1.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
			if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
			++l[i];
			g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
			if(hs[i])g2.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
			upd();
		}
		else{
			ans-=o*p[i]*hs[i]/(hs[i]+l[i]);
			if(hs[i]!=l[i])ans+=o*p[i]*hs[i]/(hs[i]+l[i]-1),g1.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
			else {ans+=o*p[i]/2;--hs[i],++t;}
			if(hs[i])g2.del(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
			--l[i];
			if(hs[i]!=l[i])g1.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]+1))));
			if(hs[i])g2.push(mk(i,o*p[i]*l[i]/(1ll*(l[i]+hs[i])*(l[i]+hs[i]-1))));
			upd();
		}
		printf("%.10Lf\n",ans); 
	}
	return 0;
}
2021/4/25 13:31
加载中...