QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515943 | #4880. Network Transfer | Yoralen | WA | 1ms | 5940kb | C++14 | 1.2kb | 2024-08-12 11:58:24 | 2024-08-12 11:58:24 |
Judging History
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]);
}
详细
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'