QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200615#7350. Test For An Internnameless_story#WA 0ms3684kbC++202.6kb2023-10-04 17:59:542023-10-04 17:59:54

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 17:59:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3684kb
  • [2023-10-04 17:59:54]
  • 提交

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: 0ms
memory: 3684kb

input:

6 4 5.25
0 0
1 0
2 1
2 2
1 3
0 2
5 4
5 3
7 1
7 2

output:

nan

result:

wrong answer Token "nan" doesn't correspond to pattern "No|Yes"