QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515091 | #4880. Network Transfer | uuku | WA | 137ms | 15064kb | C++14 | 4.6kb | 2024-08-11 15:08:24 | 2024-08-11 15:08:26 |
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;
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,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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7928kb
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: 5920kb
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: 6008kb
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: 7980kb
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: 7912kb
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: 0ms
memory: 7904kb
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: 0ms
memory: 7916kb
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: 5920kb
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: 86ms
memory: 15064kb
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: 104ms
memory: 14192kb
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: 137ms
memory: 13092kb
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: 132ms
memory: 14788kb
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: 135ms
memory: 13328kb
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: 126ms
memory: 14472kb
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: 128ms
memory: 13220kb
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: 83ms
memory: 10560kb
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'