QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200613 | #7344. Those Russian Hackers | nameless_story# | WA | 1ms | 3396kb | C++20 | 2.6kb | 2023-10-04 17:59:48 | 2023-10-04 17:59:48 |
Judging History
answer
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
typedef __float128 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;
cout<<"nan\n";
return 0;
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--)
{
db pr=p[i]/(sum[n]-sum[i]);
P=max(d[i],pr*max(F,S[n-i-1])+(1-pr)*P);
}
F=P;
// cerr<<F<<endl;
while (--m)
{
for (i=n-1; i>=0; i--)
{
db pr=p[i]/(sum[n]-sum[i]);
P=max(d[i],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: 0
Wrong Answer
time: 1ms
memory: 3396kb
input:
3 1 0.5 0.25 0.25 0.75 0.25 0.0 0.0
output:
nan
result:
wrong output format Expected double, but "nan" found