QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515066 | #4880. Network Transfer | uuku | WA | 145ms | 15064kb | C++14 | 4.6kb | 2024-08-11 14:58:17 | 2024-08-11 14:58:17 |
Judging History
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'