QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515066#4880. Network TransferuukuWA 145ms15064kbC++144.6kb2024-08-11 14:58:172024-08-11 14:58:17

Judging History

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

  • [2024-08-11 14:58:17]
  • 评测
  • 测评结果:WA
  • 用时:145ms
  • 内存:15064kb
  • [2024-08-11 14:58:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

namespace ModInt{
	template <uint32_t mod>
	struct mint
	{
		#define i32 int32_t
		#define u32 uint32_t
		#define u64 uint64_t
		static constexpr u32 get_r(){u32 ret=mod;for(i32 i=0;i<4;++i)ret*=2-mod*ret;return ret;}
		static constexpr u32 r=get_r();
		static const u32 n2=-u64(mod)%mod;
		static const u32 mod2=mod<<1;
		u32 a;
		constexpr mint():a(0){}
		constexpr mint(const int64_t &b):a(reduce(u64(b%mod+mod)*n2)){};
		static constexpr u32 reduce(const u64 &b){return (b+u64(u32(b)*u32(-r))*mod)>>32;}
		const mint &operator+=(const mint &b){if(i32(a+=b.a-mod2)<0)a+=mod2;return *this;}
		const mint &operator-=(const mint &b){if(i32(a-=b.a)<0)a+=mod2;return *this;}
		const mint &operator*=(const mint &b){a=reduce(u64(a)*b.a);return *this;}
		const mint &operator/=(const mint &b){*this*=b.inverse();return *this;}
		const mint operator+(const mint &b)const{return mint(*this)+=b;}
		const mint operator-(const mint &b)const{return mint(*this)-=b;}
		const mint operator*(const mint &b)const{return mint(*this)*=b;}
		const mint operator/(const mint &b)const{return mint(*this)/=b;}
		const bool operator==(const mint &b)const{return(a>=mod?a-mod:a)==(b.a>=mod?b.a-mod:b.a);}
		const bool operator!=(const mint &b)const{return(a>=mod?a-mod:a)!=(b.a>=mod?b.a-mod:b.a);}
		const mint operator-()const{return mint()-mint(*this);}
		const mint ksm(u64 n)const{mint ret(1);for(mint mul(*this);n;n>>=1,mul*=mul)if(n&1)ret*=mul;return ret;}
		const mint inverse()const{return ksm(mod-2);}
		friend ostream &operator<<(ostream &os, const mint &b){return os<<b.get();}
		friend istream &operator>>(istream &is, mint &b){int64_t t;is>>t;b=mint(t);return(is);}
		const u32 get()const{u32 ret=reduce(a);return ret>=mod?ret-mod:ret;}
		static const u32 get_mod(){return mod;}
	};
}
using namespace ModInt;

namespace FAST_IO{
	#define ll long long
	#define ull unsigned long long
	#define db double
	#define _8 __int128_t
	#define Get() (BUF[Pin++])
	const int LEN=1<<20;
	char BUF[LEN];
	int Pin=LEN;
	inline void flushin(){memcpy(BUF,BUF+Pin,LEN-Pin),fread(BUF+LEN-Pin,1,Pin,stdin),Pin=0;return;}
	inline char Getc(){return (Pin==LEN?(fread(BUF,1,LEN,stdin),Pin=0):0),BUF[Pin++];}
	template<typename tp>inline tp read(){(Pin+40>=LEN)?flushin():void();tp res=0;char f=1,ch=' ';for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+ch-48;return res*f;}
	template<typename tp>inline void read(tp &n){(Pin+40>=LEN)?flushin():void();tp res=0;char f=1,ch=' ';for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+ch-48;n=res*f;return;}
	inline int readstr(char *s){int len=0;char ch=Getc();while(!isalnum(ch))ch=Getc();while(isalnum(ch))s[len++]=ch,ch=Getc();return len;}
	#define Put(x) (PUF[Pout++]=x)
	char PUF[LEN];
	int Pout;
	inline void flushout(){fwrite(PUF,1,Pout,stdout),Pout=0;return;}
	inline void Putc(char x){if(Pout==LEN)flushout(),Pout=0;PUF[Pout++]=x;}
	template<typename tp>inline void write(tp a,char b='\n'){static int stk[40],top;(Pout+50>=LEN)?flushout():void();if(a<0)Put('-'),a=-a;else if(a==0)Put('0');for(top=0;a;a/=10)stk[++top]=a%10;for(;top;--top)Put(stk[top]^48);Put(b);return;}
	inline void wt_str(string s){for(char i:s)Putc(i);return;}
}
using namespace FAST_IO;

#define pii pair<int,int>
#define fi first
#define se second
#define ls (rt<<1)
#define rs (rt<<1|1)
#define Ls (tr[rt].lc)
#define Rs (tr[rt].rc)

const int N=2e5+10;
int n,w;
struct File{
	int t,s,p,id;
}file[N];
bool cmp(File a,File b)
{
	return a.t<b.t;
}
double tot_tran,sum_p;
priority_queue<pair<double,int>>q;
double ans[N];
int main()
{
	read(n),read(w);
	for(int i=1,t,s,p;i<=n;i++)
	{
		read(t),read(s),read(p);
		file[i]={t,s,p,i};
	}
	sort(file+1,file+n+1,cmp);
	ll last_time=0;
	for(int i=1;i<=n;i++)
	{
		while(!q.empty())
		{
			if((-q.top().fi-tot_tran)*sum_p/w<file[i].t-last_time)
			{
				int now=q.top().se;
				ans[file[now].id]=(-q.top().fi-tot_tran)*sum_p/w+last_time;
				tot_tran+=(-q.top().fi-tot_tran);
				sum_p-=file[now].p;
				last_time=ans[file[now].id];
				q.pop();
			}
			else break;
		}
		if(!q.empty())tot_tran+=(file[i].t-last_time)*w/sum_p;
		q.push({-(tot_tran+1.*file[i].s/file[i].p),i});
		last_time=file[i].t;
		sum_p+=file[i].p;
	}
	while(!q.empty())
	{
		int now=q.top().se;
		ans[file[now].id]=(-q.top().fi-tot_tran)*sum_p/w+last_time;
		tot_tran+=(-q.top().fi-tot_tran);
		sum_p-=file[now].p;
		last_time=ans[file[now].id];
		q.pop();
	}
	for(int i=1;i<=n;i++)
		printf("%.9lf\n",ans[i]);
	flushout();
	return 0;
}




Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 10
0 100 2
4 200 1

output:

13.000000000
30.000000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5916kb

input:

2 10
30 200 1
10 100 2

output:

50.000000000
20.000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 8048kb

input:

1 10000000
0 1 42

output:

0.000000100

result:

ok found '0.0000001', expected '0.0000001', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5916kb

input:

1 10000000
42 1 42

output:

42.000000100

result:

ok found '42.0000001', expected '42.0000001', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 8052kb

input:

1 10000000
42 10000000 42

output:

43.000000000

result:

ok found '43.0000000', expected '43.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7960kb

input:

1 10000000
10000000 1 1

output:

10000000.000000101

result:

ok found '10000000.0000001', expected '10000000.0000001', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7960kb

input:

1 10000000
1 1 100

output:

1.000000100

result:

ok found '1.0000001', expected '1.0000001', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7988kb

input:

1 1
10000000 10000000 100

output:

20000000.000000000

result:

ok found '20000000.0000000', expected '20000000.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 81ms
memory: 14492kb

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.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
2000010000000.000000000
200001000000...

result:

ok 200000 numbers

Test #10:

score: 0
Accepted
time: 119ms
memory: 12760kb

input:

200000 1
10000000 10000000 22
10000000 10000000 62
10000000 10000000 71
10000000 10000000 73
10000000 10000000 82
10000000 10000000 15
10000000 10000000 60
10000000 10000000 26
10000000 10000000 35
10000000 10000000 83
10000000 10000000 58
10000000 10000000 84
10000000 10000000 23
10000000 10000000 ...

output:

1790041363599.711425781
1390577580625.000000000
1300784647871.000000000
1280812465738.000000000
1190840487795.000000000
1859583333293.000000000
1410498166646.000000000
1750241923041.000000000
1660420857111.000000000
1180833975894.000000000
1430416379288.000000000
1170834642848.000000000
178007260865...

result:

ok 200000 numbers

Test #11:

score: 0
Accepted
time: 144ms
memory: 14380kb

input:

199293 5
9504657 9159218 4
9229606 9939393 93
9949326 9400061 74
9049202 9678955 63
9856746 9805686 100
9900514 9492706 58
9077984 9828311 42
9082259 9783365 78
9815702 9654015 95
9655893 9753916 11
9027905 9930425 9
9210664 9496857 85
9488366 9132506 56
9416678 9238290 2
9475297 9343399 28
9442121 ...

output:

372606768627.428405762
212211523109.835449219
238948123872.230499268
263425572427.884674072
197063140264.911773682
270580452150.286773682
303466986000.622192383
237141203281.056518555
203504173112.214263916
360171409173.501525879
364170087400.170715332
219530851360.010742188
270186172539.264526367
3...

result:

ok 199293 numbers

Test #12:

score: 0
Accepted
time: 139ms
memory: 13772kb

input:

199775 5
9573917 9665464 57
9498813 9469832 81
9885957 9606395 14
9397765 9003071 9
9246019 9070405 26
9740136 9081183 11
9893308 9667485 60
9912483 9414387 94
9934996 9683245 7
9359993 9793294 90
9852046 9209808 22
9704268 9048813 52
9066664 9842295 49
9894656 9914370 56
9520915 9685732 36
9507809 ...

output:

275136144311.055725098
227063686256.816986084
355194223131.173095703
363385247633.993530273
329856086338.132934570
359600178864.008300781
269538817694.780853271
201263965727.644042969
368365455611.568603516
215596634611.191314697
338462008723.713134766
277864536390.819396973
291752330618.072448730
2...

result:

ok 199775 numbers

Test #13:

score: 0
Accepted
time: 142ms
memory: 15064kb

input:

199876 10
9569180 9097026 11
9805018 9888590 69
9859588 9812730 54
9708644 9290190 38
9672977 9335125 45
9617443 9706660 56
9670948 9431976 69
9705708 9008410 2
9091288 9600793 23
9064094 9794988 56
9750869 9563190 30
9234184 9600771 22
9681961 9478086 50
9410316 9590449 15
9604218 9991066 51
957349...

output:

179887419042.662902832
127724868873.802246094
141024093836.153137207
153787797579.602050781
147195678594.592987061
138618951788.048767090
124676244712.727859497
188810727915.358398438
169163433572.910614014
139088243046.179931641
162417515047.573730469
170107993985.822021484
143081567851.488464355
1...

result:

ok 199876 numbers

Test #14:

score: 0
Accepted
time: 141ms
memory: 14016kb

input:

199977 4
9602127 9565587 73
9111223 9419029 57
9833218 9019063 97
9020206 9577308 79
9062250 9637529 67
9457065 9295138 1
9448587 9234150 78
9535931 9639433 15
9247581 9592339 40
9768195 9797367 34
9649692 9879574 35
9727787 9190412 97
9260259 9150191 43
9851295 9229529 69
9724520 9333397 67
9676184...

output:

304491725432.079956055
340031024901.070861816
234313921587.710510254
290561423211.243591309
319805991448.538757324
474840245794.306762695
286089965980.414855957
441518151406.164489746
382411218726.232177734
398221152045.854248047
396587502291.964538574
238678763269.971191406
370475808181.857238770
3...

result:

ok 199977 numbers

Test #15:

score: 0
Accepted
time: 145ms
memory: 14552kb

input:

199077 6
9634388 9960151 22
9418114 9874787 41
9769850 9225397 37
9368769 9901425 8
9489208 9902249 82
9371370 9920615 49
9263226 9036325 88
9329155 9233456 23
9366876 9584570 56
9434611 9799061 9
9473832 9195956 44
9220704 9779369 72
9801558 9822981 43
9366955 9830926 27
9770139 9638731 78
9741872 ...

output:

283688068447.783569336
254552110084.227996826
256675918163.864013672
304680637087.574768066
192633821814.078216553
242706607859.476776123
170818519401.773529053
279445660921.743408203
229155344811.827758789
303032517676.829833984
245028643740.123779297
206387689469.850158691
251159864137.463165283
2...

result:

ok 199077 numbers

Test #16:

score: -100
Wrong Answer
time: 105ms
memory: 10616kb

input:

199174 94
4939842 606 76
1166421 867 100
9051103 784 55
8172658 675 51
3743680 551 61
2613139 796 25
6619357 995 81
4244151 919 13
1565998 618 89
8971567 956 48
4453079 696 6
6507538 985 84
821657 762 98
5429287 786 27
6562208 661 86
286640 615 36
6512669 689 74
219589 615 49
8412173 719 58
8817089 ...

output:

4939848.446808510
1166430.223404255
9051111.340425532
8172665.180851064
3743685.861702128
2613147.468085106
6619367.585106383
4244160.776595744
1566004.574468085
8971577.170212766
4453091.248226950
6507549.556363156
821665.106382979
5429295.342969473
6562215.031914894
286647.117021277
6512680.579212...

result:

wrong answer 63rd numbers differ - expected: '445143.4255319', found: '445142.4297872', error = '0.0000022'