QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515072#4880. Network TransferuukuWA 197ms29132kbC++144.6kb2024-08-11 15:00:562024-08-11 15:00:58

Judging History

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

  • [2024-08-11 15:00:58]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:29132kb
  • [2024-08-11 15:00:56]
  • 提交

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{
	long double t,s,p;
	int id;
}file[N];
bool cmp(File a,File b)
{
	return a.t<b.t;
}
long double tot_tran,sum_p;
priority_queue<pair<long double,int>>q;
long 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)/w*sum_p<file[i].t-last_time)
			{
				int now=q.top().se;
				ans[file[now].id]=(-q.top().fi-tot_tran)/w*sum_p+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)/sum_p*w;
		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)/w*sum_p+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: 7960kb

input:

2 10
0 100 2
4 200 1

output:

13.000000000
30.000000000

result:

ok 2 numbers

Test #2:

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

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: 7940kb

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: 7820kb

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: 1ms
memory: 7824kb

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: 7840kb

input:

1 10000000
10000000 1 1

output:

10000000.000000100

result:

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

Test #7:

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

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: 0ms
memory: 7904kb

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: 119ms
memory: 28032kb

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: 165ms
memory: 28888kb

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.711462498
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: 178ms
memory: 27756kb

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.428377211
212211523109.835485741
238948123872.230517641
263425572427.884648368
197063140264.911756277
270580452150.286765590
303466986000.622168958
237141203281.056511953
203504173112.214276880
360171409173.501527518
364170087400.170714974
219530851360.010747507
270186172539.264515474
3...

result:

ok 199293 numbers

Test #12:

score: 0
Accepted
time: 197ms
memory: 28856kb

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.055717409
227063686256.816980436
355194223129.173111111
363385247630.993542522
329856086337.132927835
359600178861.008326858
269538817694.780848190
201263965727.644071728
368365455608.568591088
215596634611.191327229
338462008721.713159144
277864536390.819408149
291752330618.072439611
2...

result:

ok 199775 numbers

Test #13:

score: 0
Accepted
time: 192ms
memory: 27852kb

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:

179887419041.662899971
127724868873.802253462
141024093835.153149039
153787797578.602048352
147195678593.592970237
138618951787.048760533
124676244712.727857903
188810727914.358397663
169163433571.910607472
139088243045.179929599
162417515046.573736593
170107993984.822006211
143081567850.488458693
1...

result:

ok 199876 numbers

Test #14:

score: 0
Accepted
time: 185ms
memory: 29132kb

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:

304491725431.079947501
340031024901.070825845
234313921587.710536167
290561423211.243575186
319805991448.538753867
474840245791.306748182
286089965980.414818943
441518151403.164481193
382411218726.232158780
398221152045.854282677
396587502291.964566171
238678763269.971223757
370475808181.857241750
3...

result:

ok 199977 numbers

Test #15:

score: 0
Accepted
time: 185ms
memory: 27592kb

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:

283688068446.783597201
254552110083.227984056
256675918162.864021629
304680637086.574750870
192633821814.078216240
242706607858.476762697
170818519401.773549050
279445660920.743428051
229155344810.827748388
303032517675.829812706
245028643739.123760581
206387689469.850167841
251159864136.463170901
2...

result:

ok 199077 numbers

Test #16:

score: -100
Wrong Answer
time: 137ms
memory: 20968kb

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.446808511
1166430.223404255
9051111.340425532
8172665.180851064
3743685.861702128
2613147.468085106
6619367.585106383
4244160.776595745
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'