QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515943#4880. Network TransferYoralenWA 1ms5940kbC++141.2kb2024-08-12 11:58:242024-08-12 11:58:24

Judging History

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

  • [2024-08-12 11:58:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5940kb
  • [2024-08-12 11:58:24]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int N=200005;
int n,m;
struct node{
	double t,p;int i;
	bool operator <(node A)const{return t<A.t;}
};
struct Op{double s,t,p;}a[N];
bool cmp(Op A,Op B){return A.s<B.s;}
multiset<node>S;
double w,f[N];
int main(){
	int i;
	scanf("%d%lf",&n,&w);
	for(i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i].s,&a[i].t,&a[i].p);
	sort(a+1,a+1+n,cmp);
	double sp=0,k=1,b=0;
	for(i=1;i<=n;i++){
		double t0=a[i].s,p0=a[i].p;
		while(S.size()){
			node u=*(S.begin());
			if(u.t<=(t0-b)/k){
				f[u.i]=u.t*k+b;
				double k1=(sp-u.p)/sp,b1=f[u.i]/sp*u.p;
				b=b1+k1*b,k=k*k1;sp-=u.p;
				S.erase(S.begin());
			}
			else break;
		}
		if(S.size()){
			double k1=(sp+p0)/sp,b1=-t0/sp*p0;
			b=b1+k1*b,k=k*k1;
		}
		else k=1,b=0;
//		printf("%lf %lf\n",k,b);
		sp+=p0;f[i]=t0+(a[i].t)/(p0/sp*w);
//		printf("%.6lf\n",f[i]);
		S.insert((node){(f[i]-b)/k,p0,i});
	}
//	printf("%d\n",S.size());
	while(S.size()){
		node u=*(S.begin());
		f[u.i]=u.t*k+b;
		double k1=(sp-u.p)/sp,b1=f[u.i]/sp*u.p;
		b=b1+k1*b,k=k*k1;sp-=u.p;
		S.erase(S.begin());
	}
	for(i=1;i<=n;i++)printf("%.9lf\n",f[i]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5940kb

input:

2 10
0 100 2
4 200 1

output:

13.000000000
30.000000000

result:

ok 2 numbers

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

2 10
30 200 1
10 100 2

output:

20.000000000
50.000000000

result:

wrong answer 1st numbers differ - expected: '50.0000000', found: '20.0000000', error = '0.6000000'