QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200659 | #7344. Those Russian Hackers | nameless_story | TL | 1463ms | 157336kb | C++20 | 2.7kb | 2023-10-04 18:13:45 | 2023-10-04 18:13:46 |
Judging History
answer
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
typedef double db;
namespace FFT
{
const int N=1<<20;
using db=long double;
const db pi=3.1415926535897932384626434;
using cp=complex<db>;
const cp I{0,-1};
cp Wn[N];
int r[N];
void init(int n)
{
static int preone=-1;
if (n==preone) return;
preone=n;
int b,i;
b=__builtin_ctz(n)-1;
for (i=1; i<n; i++) r[i]=r[i>>1]>>1|(i&1)<<b;
for (i=0; i<n; i++) Wn[i]={cos(pi*i/n),sin(pi*i/n)};
}
int cal(int x) { return 1u<<32-__builtin_clz(max(x,2)-1); }
struct Q
{
vector<cp> a;
int deg;
cp *pt() { return a.data(); }
Q(int n=0)
{
deg=n;
a.resize(cal(n));
}
void dft(int xs=0)
{
int i,j,k,l,n=a.size(),d;
cp w,wn,b,c,*f=pt(),*g,*a=f;
init(n);
if (xs) reverse(a+1,a+n);
for (i=0; i<n; i++) if (i<r[i]) swap(a[i],a[r[i]]);
for (i=1,d=0; i<n; i=l,d++)
{
l=i<<1;
for (j=0; j<n; j+=l)
{
f=a+j; g=f+i;
for (k=0; k<i; k++)
{
w=Wn[k*(n>>d)];
b=f[k]; c=g[k]*w;
f[k]=b+c;
g[k]=b-c;
}
}
}
if (xs) for (i=0; i<n; i++) a[i]/=n;
}
void operator|=(Q o)
{
int n=deg+o.deg-1,m=cal(n),i;
a.resize(m); o.a.resize(m);
dft(); o.dft();
for (i=0; i<m; i++) a[i]*=o.a[i];
deg=n;
dft(1);
for (i=n; i<m; i++) a[i]={ };
}
Q operator|(Q o) const { o|=*this; return o; }
};
}
#define poly FFT::Q
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cout<<fixed<<setprecision(15);
int n,m,i,j;
cin>>n>>m;
vector<db> p(n),q(n*2-1),c(n+1),d(n+1),S(n*2-1),sum(n+1);
for (db &x:p)
{
string s;
cin>>s;
x=stold(s);
}
for (i=1; i<=n*2-2; i++)
{
string s;
cin>>s;
q[i]=stold(s);
S[i]=S[i-1]+q[i];
}
{
// cerr<<"!\n";
poly F(n);
for (i=0; i<n; i++) F.a[i]=p[n-i-1];
{
poly G(n+1);
for (i=0; i<=n; i++) G.a[i]=S[i];
G|=F;
for (i=0; i<n; i++) d[i]=G.a[n-i-1].real();
}
{
poly G(n*2-1);
for (i=0; i<=n*2-2; i++) G.a[i]=S[i];
G|=F;
for (i=0; i<n; i++) c[i]=G.a[2*n-i-1].real();
}
}
// for (i=0; i<n; i++) cerr<<c[i]<<' '<<d[i]<<endl;
db F=0;
db P=F;
sum[0]=0; for (i=0; i<n; ++i) sum[i+1]=sum[i]+p[i];
for (i=0; i<n; ++i) d[i]/=sum[n]-sum[i];
for (i=n-1; i>=0; i--) if (sum[n]-sum[i])
{
db pr=p[i]/(sum[n]-sum[i]);
P=max(d[i],pr*max(F,S[n-i-1])+(1-pr)*P);
// cerr<<"dp"<<' '<<i<<' '<<pr<<' '<<d[i]<<' '<<S[n-i-1]<<endl;
}
F=P;
// cerr<<F<<endl;
while (--m)
{
for (i=n-1; i>=0; i--) if (sum[n]-sum[i])
{
db pr=p[i]/(sum[n]-sum[i]);
P=pr*max(F,c[i+1])+(1-pr)*P;
}
F=P;
}
cout<<(long double)F<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6044kb
input:
3 1 0.5 0.25 0.25 0.75 0.25 0.0 0.0
output:
0.687500000000000
result:
ok found '0.6875000', expected '0.6875000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5980kb
input:
3 2 0.3 0.4 0.3 0.0 0.0 0.0 1.0
output:
0.090000000000000
result:
ok found '0.0900000', expected '0.0900000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
3 1 0.5 0.2 0.3 1.0 0.0 0.0 0.0
output:
0.800000000000000
result:
ok found '0.8000000', expected '0.8000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
2 1 1.0 0.0 0.7 0.3
output:
0.700000000000000
result:
ok found '0.7000000', expected '0.7000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
2 2 0.0 1.0 0.6 0.4
output:
0.600000000000000
result:
ok found '0.6000000', expected '0.6000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 6120kb
input:
3 1 0.1 0.1 0.8 1.0 0.0 0.0 0.0
output:
0.900000000000000
result:
ok found '0.9000000', expected '0.9000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
2 1 0.196570 0.803430 0.417660 0.582340
output:
0.335560573800000
result:
ok found '0.3355606', expected '0.3355606', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 6040kb
input:
2 1 0.392496 0.607504 1.000000 0.000000
output:
0.607504000000000
result:
ok found '0.6075040', expected '0.6075040', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6020kb
input:
10 1 0.012643 0.123624 0.053820 0.040365 0.028873 0.020157 0.055711 0.484945 0.098421 0.081441 0.085328 0.047990 0.714931 0.138813 0.012938 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.901027547899000
result:
ok found '0.9010275', expected '0.9010275', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
10 1 0.006649 0.073200 0.000565 0.045068 0.112668 0.035625 0.046072 0.103194 0.005569 0.571390 0.195573 0.074055 0.047683 0.369439 0.161507 0.054811 0.055588 0.037380 0.003964 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.853833380837000
result:
ok found '0.8538334', expected '0.8538334', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 6020kb
input:
10 1 0.145228 0.019318 0.105821 0.185187 0.088991 0.042625 0.024569 0.088478 0.047174 0.252609 0.018498 0.107130 0.001316 0.120833 0.069263 0.099338 0.005632 0.009075 0.036279 0.023135 0.008573 0.029578 0.025695 0.067194 0.023536 0.116172 0.157449 0.081304
output:
0.306330006553000
result:
ok found '0.3063300', expected '0.3063300', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
10 10 0.044299 0.160436 0.044139 0.088241 0.291281 0.136777 0.020766 0.124310 0.013255 0.076496 0.081824 0.025457 0.068874 0.265701 0.558144 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.999983853958751
result:
ok found '0.9999839', expected '0.9999839', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 6020kb
input:
10 10 0.098756 0.001607 0.002767 0.264946 0.282086 0.080842 0.027809 0.031328 0.176685 0.033174 0.072398 0.177002 0.005668 0.017867 0.488488 0.060093 0.085645 0.025416 0.067423 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.986428786179379
result:
ok found '0.9864288', expected '0.9864288', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
10 10 0.429937 0.091639 0.001306 0.006129 0.006155 0.171890 0.227093 0.040566 0.003681 0.021604 0.041201 0.062705 0.028561 0.106362 0.004036 0.034025 0.097426 0.071704 0.050975 0.005562 0.042348 0.065488 0.055791 0.033996 0.101538 0.032639 0.105819 0.059824
output:
0.628303052313434
result:
ok found '0.6283031', expected '0.6283031', error '0.0000000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 6184kb
input:
1000 1000 0.000186 0.000277 0.000747 0.004770 0.001251 0.001097 0.001523 0.000697 0.002943 0.000903 0.000046 0.000063 0.000033 0.000233 0.000333 0.000385 0.000192 0.001261 0.002266 0.000046 0.001039 0.001668 0.000955 0.002996 0.000001 0.000635 0.001404 0.000237 0.000757 0.000273 0.001566 0.000076 0....
output:
0.999999999999998
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 6124kb
input:
1000 1000 0.000547 0.000752 0.000703 0.001254 0.003381 0.000643 0.002170 0.000597 0.001286 0.005326 0.000228 0.000866 0.002296 0.000276 0.001162 0.000225 0.001080 0.002429 0.001119 0.001858 0.001548 0.000080 0.002263 0.000292 0.000358 0.000841 0.000658 0.001286 0.002226 0.004054 0.000382 0.001406 0....
output:
0.999998043068137
result:
ok found '0.9999980', expected '0.9999980', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 6096kb
input:
1000 1000 0.000362 0.001464 0.000148 0.000631 0.000095 0.000870 0.000089 0.000110 0.000545 0.000621 0.001660 0.000251 0.000261 0.001025 0.001456 0.002287 0.000990 0.001421 0.000920 0.001709 0.002256 0.002731 0.000697 0.002399 0.003296 0.000171 0.000584 0.000437 0.001456 0.000772 0.000126 0.000171 0....
output:
0.758192052456725
result:
ok found '0.7581921', expected '0.7581921', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5864kb
input:
2 300000 0.044919 0.955081 1.000000 0.000000
output:
0.999999999999999
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #19:
score: 0
Accepted
time: 3ms
memory: 6108kb
input:
2 300000 0.922991 0.077009 0.216415 0.783585
output:
0.276758097265000
result:
ok found '0.2767581', expected '0.2767581', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1207ms
memory: 157104kb
input:
300000 1 0.000003 0.000000 0.000001 0.000003 0.000006 0.000001 0.000001 0.000001 0.000003 0.000003 0.000001 0.000003 0.000000 0.000005 0.000002 0.000001 0.000001 0.000002 0.000003 0.000002 0.000007 0.000000 0.000010 0.000000 0.000001 0.000000 0.000005 0.000009 0.000001 0.000002 0.000001 0.000006 0.0...
output:
0.500640852639198
result:
ok found '0.5006409', expected '0.5006409', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1324ms
memory: 157336kb
input:
300000 1 0.000007 0.000000 0.000003 0.000020 0.000001 0.000001 0.000000 0.000009 0.000000 0.000004 0.000000 0.000002 0.000001 0.000001 0.000002 0.000012 0.000001 0.000004 0.000001 0.000004 0.000003 0.000005 0.000013 0.000001 0.000002 0.000007 0.000001 0.000001 0.000005 0.000003 0.000001 0.000002 0.0...
output:
0.250560883052075
result:
ok found '0.2505609', expected '0.2505609', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1305ms
memory: 157096kb
input:
300000 10 0.000001 0.000001 0.000000 0.000000 0.000000 0.000001 0.000004 0.000001 0.000007 0.000004 0.000003 0.000002 0.000000 0.000004 0.000002 0.000001 0.000020 0.000001 0.000000 0.000003 0.000010 0.000001 0.000002 0.000013 0.000001 0.000007 0.000003 0.000006 0.000001 0.000001 0.000003 0.000001 0....
output:
0.979810412919423
result:
ok found '0.9798104', expected '0.9798104', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1318ms
memory: 157108kb
input:
300000 10 0.000002 0.000002 0.000000 0.000001 0.000001 0.000001 0.000001 0.000014 0.000000 0.000004 0.000001 0.000002 0.000006 0.000000 0.000002 0.000002 0.000005 0.000001 0.000000 0.000001 0.000000 0.000003 0.000000 0.000001 0.000002 0.000000 0.000007 0.000000 0.000003 0.000002 0.000001 0.000003 0....
output:
0.675031975313002
result:
ok found '0.6750320', expected '0.6750320', error '0.0000000'
Test #24:
score: 0
Accepted
time: 1327ms
memory: 157140kb
input:
300000 100 0.000000 0.000002 0.000003 0.000007 0.000001 0.000004 0.000003 0.000000 0.000001 0.000000 0.000003 0.000001 0.000002 0.000000 0.000008 0.000002 0.000003 0.000002 0.000000 0.000004 0.000005 0.000004 0.000003 0.000004 0.000003 0.000001 0.000000 0.000005 0.000005 0.000003 0.000006 0.000002 0...
output:
0.999617530758079
result:
ok found '0.9996175', expected '0.9996175', error '0.0000000'
Test #25:
score: 0
Accepted
time: 1463ms
memory: 157332kb
input:
300000 100 0.000000 0.000006 0.000000 0.000001 0.000001 0.000003 0.000005 0.000005 0.000004 0.000000 0.000004 0.000001 0.000001 0.000000 0.000002 0.000001 0.000001 0.000001 0.000003 0.000007 0.000004 0.000000 0.000002 0.000002 0.000003 0.000002 0.000012 0.000003 0.000001 0.000002 0.000003 0.000000 0...
output:
0.740882930906066
result:
ok found '0.7408829', expected '0.7408829', error '0.0000000'
Test #26:
score: -100
Time Limit Exceeded
input:
300000 300000 0.000000 0.000007 0.000002 0.000003 0.000003 0.000004 0.000006 0.000008 0.000002 0.000001 0.000002 0.000001 0.000000 0.000005 0.000012 0.000003 0.000000 0.000014 0.000000 0.000000 0.000003 0.000008 0.000001 0.000001 0.000002 0.000001 0.000001 0.000005 0.000005 0.000000 0.000003 0.00000...