QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53609 | #4880. Network Transfer | KING_UT# | WA | 294ms | 12988kb | C++20 | 1.3kb | 2022-10-05 14:35:05 | 2022-10-05 14:35:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
template<class t>using vc=vector<t>;
#define a first
#define b second
using vi=vc<int>;
using ld=double;
const ld inf=1./0;
using T=tuple<int,int,int,int>;
void slv(){
int n;cin>>n;
double w;cin>>w;
vc<T> ls(n);
vi ps(n);
rep(i,n){
int t,s,p;cin>>t>>s>>p;
ls[i]=T(t,s,p,i);
ps[i]=p;
}
sort(all(ls));
vc<ld> ans(n);
ld cur=0;
int psum=0;
using P=pair<ld,int>;
priority_queue<P,vc<P>,greater<P>> pq;
ld b=0;
auto next_finish=[&](){
if(pq.empty())return inf;
return cur+(pq.top().a+b)*psum;
};
auto add=[&](ld s,ld p,int i){
pq.emplace(s/(w*p)-b,i);
psum+=ps[i];
};
auto pop=[&](){
auto [tmp,i]=pq.top();pq.pop();
//cerr<<i<<" "<<tmp+b<<endl;
psum-=ps[i];
ans[i]=cur;
};
auto proceed=[&](ld t){
int e=t-cur;cur=t;
if(psum==0)b=0;
else b-=e/psum;
};
int head=0;
while(1){
double z=next_finish();
if(head<n&&get<0>(ls[head])<z){
auto [t,s,p,i]=ls[head++];
proceed(t);
add(s,p,i);
}else{
if(z==inf)break;
proceed(z);
pop();
}
}
rep(i,n)cout<<ans[i]<<"\n";
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(10);
slv();
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3828kb
input:
2 10 0 100 2 4 200 1
output:
13.0000000000 30.0000000000
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
2 10 30 200 1 10 100 2
output:
50.0000000000 20.0000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
1 10000000 0 1 42
output:
0.0000001000
result:
ok found '0.0000001', expected '0.0000001', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
1 10000000 42 1 42
output:
42.0000001000
result:
ok found '42.0000001', expected '42.0000001', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
1 10000000 42 10000000 42
output:
43.0000000000
result:
ok found '43.0000000', expected '43.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
1 10000000 10000000 1 1
output:
10000000.0000001006
result:
ok found '10000000.0000001', expected '10000000.0000001', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
1 10000000 1 1 100
output:
1.0000001000
result:
ok found '1.0000001', expected '1.0000001', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 1 10000000 10000000 100
output:
20000000.0000000000
result:
ok found '20000000.0000000', expected '20000000.0000000', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 294ms
memory: 12988kb
input:
200000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10...
output:
2000010000000.0000000000 4002147389263.0000000000 6006422146315.0000000000 8012834249682.0000000000 10021383677890.0000000000 12032070409465.0000000000 14044894422933.0000000000 16059855696820.0000000000 18076954209652.0000000000 20096189939955.0000000000 22117562866255.0000000000 24141072967078.000...
result:
wrong answer 2nd numbers differ - expected: '2000010000000.0007324', found: '4002147389263.0000000', error = '1.0010637'