QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515070 | #4880. Network Transfer | uuku | WA | 161ms | 19704kb | C++14 | 4.6kb | 2024-08-11 14:59:07 | 2024-08-11 14:59:07 |
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;
}
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'