QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515070#4880. Network TransferuukuWA 161ms19704kbC++144.6kb2024-08-11 14:59:072024-08-11 14:59:07

Judging History

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

  • [2024-08-11 14:59:07]
  • 评测
  • 测评结果:WA
  • 用时:161ms
  • 内存:19704kb
  • [2024-08-11 14:59:07]
  • 提交

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




详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7900kb

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

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

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

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

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

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

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

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: 94ms
memory: 17084kb

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: 134ms
memory: 19280kb

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.711460829
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: 160ms
memory: 18804kb

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.835475251
238948123872.230517060
263425572427.884663820
197063140264.911751926
270580452150.286762565
303466986000.622173220
237141203281.056510687
203504173112.214263827
360171409173.501526058
364170087400.170713454
219530851360.010748282
270186172539.264523506
3...

result:

ok 199293 numbers

Test #12:

score: 0
Accepted
time: 156ms
memory: 18240kb

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:

275136144310.055724233
227063686256.816992238
355194223128.173114300
363385247629.993543684
329856086335.132926494
359600178860.008327127
269538817693.780851290
201263965727.644067183
368365455607.568591088
215596634611.191312432
338462008720.713159382
277864536389.819408536
291752330617.072445124
2...

result:

ok 199775 numbers

Test #13:

score: 0
Accepted
time: 161ms
memory: 19124kb

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.662900105
127724868873.802258894
141024093836.153149799
153787797579.602048919
147195678594.592970103
138618951788.048764244
124676244712.727852717
188810727915.358397663
169163433572.910609186
139088243046.179929748
162417515047.573737487
170107993985.822007462
143081567851.488461435
1...

result:

ok 199876 numbers

Test #14:

score: 0
Accepted
time: 140ms
memory: 18844kb

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.079948276
340031024900.070839703
234313921587.710523114
290561423211.243561119
319805991447.538757652
474840245790.306748182
286089965980.414839983
441518151402.164482057
382411218725.232158661
398221152044.854268700
396587502290.964568049
238678763269.971222058
370475808180.857241124
3...

result:

ok 199977 numbers

Test #15:

score: 0
Accepted
time: 157ms
memory: 19704kb

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.783598125
254552110083.227982178
256675918162.864020035
304680637086.574750870
192633821814.078209877
242706607858.476771042
170818519401.773548722
279445660920.743424505
229155344810.827740356
303032517675.829812706
245028643739.123761222
206387689469.850151971
251159864136.463173181
2...

result:

ok 199077 numbers

Test #16:

score: -100
Wrong Answer
time: 98ms
memory: 12108kb

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'