QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200659#7344. Those Russian Hackersnameless_storyTL 1463ms157336kbC++202.7kb2023-10-04 18:13:452023-10-04 18:13:46

Judging History

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

  • [2023-10-04 18:13:46]
  • 评测
  • 测评结果:TL
  • 用时:1463ms
  • 内存:157336kb
  • [2023-10-04 18:13:45]
  • 提交

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;
}

详细

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...

output:


result: