QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53609#4880. Network TransferKING_UT#WA 294ms12988kbC++201.3kb2022-10-05 14:35:052022-10-05 14:35:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 14:35:06]
  • 评测
  • 测评结果:WA
  • 用时:294ms
  • 内存:12988kb
  • [2022-10-05 14:35:05]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'