QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515072 | #4880. Network Transfer | uuku | WA | 197ms | 29132kb | C++14 | 4.6kb | 2024-08-11 15:00:56 | 2024-08-11 15:00:58 |
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{
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;
}
详细
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'