QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515093#4880. Network TransferuukuWA 143ms18124kbC++144.6kb2024-08-11 15:08:522024-08-11 15:08:53

Judging History

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

  • [2024-08-11 15:08:53]
  • 评测
  • 测评结果:WA
  • 用时:143ms
  • 内存:18124kb
  • [2024-08-11 15:08:52]
  • 提交

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)
#define int ll
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;
priority_queue<pair<double,int>>q;
double ans[N];
signed 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,sum_p=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+=1.*(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("%.6lf\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: 7828kb

input:

2 10
0 100 2
4 200 1

output:

13.000000
30.000000

result:

ok 2 numbers

Test #2:

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

input:

2 10
30 200 1
10 100 2

output:

50.000000
20.000000

result:

ok 2 numbers

Test #3:

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

input:

1 10000000
0 1 42

output:

0.000000

result:

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

Test #4:

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

input:

1 10000000
42 1 42

output:

42.000000

result:

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

Test #5:

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

input:

1 10000000
42 10000000 42

output:

43.000000

result:

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

Test #6:

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

input:

1 10000000
10000000 1 1

output:

10000000.000000

result:

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

Test #7:

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

input:

1 10000000
1 1 100

output:

1.000000

result:

ok found '1.0000000', expected '1.0000001', error '0.0000001'

Test #8:

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

input:

1 1
10000000 10000000 100

output:

20000000.000000

result:

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

Test #9:

score: 0
Accepted
time: 92ms
memory: 16376kb

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.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
2000010000000.000000
200001...

result:

ok 200000 numbers

Test #10:

score: 0
Accepted
time: 114ms
memory: 16552kb

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.711426
1390577580625.000000
1300784647871.000000
1280812465738.000000
1190840487795.000000
1859583333293.000000
1410498166646.000000
1750241923041.000000
1660420857111.000000
1180833975894.000000
1430416379288.000000
1170834642848.000000
1780072608659.000000
1610417249970.000000
125084...

result:

ok 200000 numbers

Test #11:

score: 0
Accepted
time: 129ms
memory: 15780kb

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.428406
212211523109.835449
238948123872.230499
263425572427.884674
197063140264.911774
270580452150.286774
303466986000.622192
237141203281.056519
203504173112.214264
360171409173.501526
364170087400.170715
219530851360.010742
270186172539.264526
376567206906.723755
326396074602.182129
...

result:

ok 199293 numbers

Test #12:

score: 0
Accepted
time: 143ms
memory: 17980kb

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.055725
227063686256.816986
355194223131.173096
363385247633.993530
329856086338.132935
359600178864.008301
269538817694.780853
201263965727.644043
368365455611.568604
215596634611.191315
338462008723.713135
277864536390.819397
291752330618.072449
279643190333.182678
314523489282.537720
...

result:

ok 199775 numbers

Test #13:

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

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.662903
127724868873.802246
141024093836.153137
153787797579.602051
147195678594.592987
138618951788.048767
124676244712.727859
188810727915.358398
169163433572.910614
139088243046.179932
162417515047.573730
170107993985.822021
143081567851.488464
176681644096.945435
144626655640.359436
...

result:

ok 199876 numbers

Test #14:

score: 0
Accepted
time: 129ms
memory: 18124kb

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.079956
340031024901.070862
234313921587.710510
290561423211.243591
319805991448.538757
474840245794.306763
286089965980.414856
441518151406.164490
382411218726.232178
398221152045.854248
396587502291.964539
238678763269.971191
370475808181.857239
307996701136.657593
314703521360.256531
...

result:

ok 199977 numbers

Test #15:

score: 0
Accepted
time: 133ms
memory: 17064kb

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.783569
254552110084.227997
256675918163.864014
304680637087.574768
192633821814.078217
242706607859.476776
170818519401.773529
279445660921.743408
229155344811.827759
303032517676.829834
245028643740.123779
206387689469.850159
251159864137.463165
275605232148.213745
195456279206.439026
...

result:

ok 199077 numbers

Test #16:

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

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.446809
1166430.223404
9051111.340426
8172665.180851
3743685.861702
2613147.468085
6619367.585106
4244160.776596
1566004.574468
8971577.170213
4453091.248227
6507549.556363
821665.106383
5429295.342969
6562215.031915
286647.117021
6512680.579212
219602.085106
8412180.648936
8817102.836979
687...

result:

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