QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278997#6565. Game Show Eliminationucup-team191AC ✓7273ms443300kbC++236.2kb2023-12-08 00:48:452023-12-08 00:48:46

Judging History

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

  • [2023-12-08 00:48:46]
  • 评测
  • 测评结果：AC
  • 用时：7273ms
  • 内存：443300kb
查看
  • [2023-12-08 00:48:45]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=502,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int n,k;
double dp[N*N/2][(1<<9)+10],k2k[50],subp[50][50],an[1010];
int ind[1010][1010];
vector<pii> broj;

double probv(int i,int x)
{
	//i..i+k-1
	if (i>x) return 1;
	if (i+k-1<x) return 0;
	return k2k[2*(i+k-x)-1];
}

vector<pair<pii,int>> ntran[20][(1<<9)+10];
vector<double> nprob[20][(1<<9)+10];

vector<double> getMal()
{
	if (k==10) return {2.9272933166,3.5373161569,4.2811822033,5.1312206602,6.0539327790,7.0191885099,8.0057023991,9.0012910303,10.0001652077,11};
	if (k==9) return {2.8411212285,3.4643592446,4.2273243674,5.0969425982,6.0352816658,7.0105742428,8.0023873942,9.0003025184,10.0000000000};
	if (k==8) return {2.7512630513,3.3900737271,4.1750068651,5.0660215194,6.0201465578,7.0045578589,8.0005725931,9.0000000000};
	if (k==7) return {2.6572867358,3.3148182612,4.1252892061,5.0395180406,6.0090390261,7.0011293865,8.0000000000};
	if (k==6) return {2.5586948349,3.2393091440,4.0797854306,5.0187532139,6.0023472144,7.0000000000};
	if (k==5) return {2.4549381277,3.1649655060,4.0409851562,5.0052199176,6.0000000000};
	if (k==4) return {2.3454995598,3.0946857154,4.0126933559,5.0000000000};
	if (k==3) return {2.2302561681,3.0347656711,4.0000000000};
	if (k==2) return {2.1111111111,3.0000000000};
	return {};
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	//n=1000;
	//k=10;
	for (int i=0;i<=2*k;++i) k2k[i]=i*0.5/k;
	for (int i=n-1;i>=0;--i) for (int j=i-1;j>=0;--j)
	{
		ind[j][i]=broj.size();
		broj.pb({j,i});
	}
	for (int dif=1;dif<=k;++dif) for (int b=0;b<(1<<(k-1));++b)
	{
		int pr=2*k,dr=2*k-dif;
		vi in;
		in.pb(pr);
		in.pb(dr);
		for (int i=0;i<k-1;++i) if ((b>>i)&1) in.pb(dr-i-1);
		vector<pair<pii,int>> trans;
		for (int i=0;i<(int)in.size();++i)
		{
			vi nex=in;
			nex.erase(nex.begin()+i);
			if (nex.size()==1) nex.pb(dr-k);
			for (int j=dr-k;j>nex[1]-k;--j)
			{
				if (j==nex.back()) continue;
				nex.pb(j);
			}
			int nb=0;
			for (int j=2;j<(int)nex.size();++j) nb|=1<<(nex[1]-nex[j]-1);
			trans.pb({{pr-nex[0],dr-nex[1]},nb});
		}
		ntran[dif][b]=trans;
		int ins=in.size();
		vector<double> novp(in.size());
		for (int x=dr;x<dr+k;++x)
		{
			for (int b1=1;b1<(1<<ins);++b1)
			{
				bool ok=1;
				for (int i=0;i<ins;++i) if ((b1>>i)&1)
				{
					if (in[i]>x || in[i]+k-1<x) ok=0;
				}
				if (!ok) continue;
				int ppcnt=__builtin_popcount(b1);
				double prox=pow(1./k,ppcnt);
				for (int vec=0;vec<ins;++vec) for (int dru=0;dru<ins;++dru) if (vec!=dru && ((b1>>dru)&1)==1)
				{
					if ((b1>>vec)&1)
					{
						double prox1=prox/(ppcnt*(ppcnt-1));
						for (int i=0;i<ins;++i) if (!((b1>>i)&1))
						{
							//[in[i],in[i]+k]<x
							if (in[i]>x) prox1=0;
							else if (in[i]+k<x) continue;
							else prox1*=(x-in[i])*1./k;
						}
						novp[dru]+=prox1;
					}
					else
					{
						double prox1=prox/ppcnt;
						for (int i=0;i<ins;++i) if (!((b1>>i)&1))
						{
							if (i==vec)
							{
								//[in[i],in[i]+k]>x+1
								if (in[i]+k<=x) prox1=0;
								else if (in[i]>x+1) continue;
								else prox1*=(in[i]+k-(x+1))*1./k;
							}
							else
							{
								//[in[i],in[i]+k]<x
								if (in[i]>x) prox1=0;
								else if (in[i]+k<x) continue;
								else prox1*=(x-in[i])*1./k;
							}
						}
						novp[dru]+=prox1;
					}
				}
			}
		}
		nprob[dif][b]=novp;
		//cout<<dif<<' '<<b<<en;
		//for (auto x: novp) cout<<x<<' ',su+=x;
		//cout<<su<<en;
	}
	//cout<<en;
	if (n<=400)
	{
		dp[ind[n-2][n-1]][(1<<min(n-2,k-1))-1]=1;
		for (int pr=n-1;pr>=1;--pr) for (int dr=pr-1;dr>=0;--dr) for (int b=(1<<min(dr,k-1))-1;b>=0;--b)
		{
			double cpp=dp[ind[dr][pr]][b];
			if (cpp<1e-20) continue;
			vi in;
			in.pb(pr);
			in.pb(dr);
			for (int i=0;i<min(dr,k-1);++i) if ((b>>i)&1) in.pb(dr-i-1);
			int elimhere=min(dr,k-1)-__builtin_popcount(b),elimbef=n-dr-2;
			int elim=elimhere+elimbef,rank=n-elim;
			int dif=min(k,pr-dr),ins=ntran[dif][b].size();
			//cout<<cpp<<' '<<pr<<' '<<dr<<' '<<b<<en;
			for (int ndr=0;ndr<ins;++ndr)
			{
				an[in[ndr]]+=rank*cpp*nprob[dif][b][ndr];
				if (rank>2)
				{
					int nnpr=pr-ntran[dif][b][ndr].x.x,nndr=dr-ntran[dif][b][ndr].x.y;
					int nb=ntran[dif][b][ndr].y;
					if (nndr<k-1)
					{
						nb&=(1<<nndr)-1;
					}
					//cout<<"MAK "<<in[ndr]<<": "<<nnpr<<' '<<nndr<<' '<<nb<<en;
					dp[ind[nndr][nnpr]][nb]+=cpp*nprob[dif][b][ndr];
				}
				else
				{
					assert(ins==2);
					an[in[1-ndr]]+=cpp*nprob[dif][b][ndr];
				}
			}
			
			//cout<<cpp<<en;
		}
	}
	else
	{
		const int U=102,MAX=n-U;
		dp[ind[n-2][n-1]][(1<<min(n-2,k-1))-1]=1;
		int maind=0;
		for (int pr=n-1;pr>=MAX;--pr) for (int dr=pr-1;dr>=0;--dr) for (int b=(1<<min(dr,k-1))-1;b>=0;--b)
		{
			double cpp=dp[ind[dr][pr]][b];
			if (ind[dr][pr]>maind)
			{
				maind=ind[dr][pr];
				//if (maind%1000==0) cout<<dr<<' '<<pr<<' '<<ind[dr][pr]<<endl;
			}
			if (cpp<1e-15) continue;
			vi in;
			in.pb(pr);
			in.pb(dr);
			for (int i=0;i<min(dr,k-1);++i) if ((b>>i)&1) in.pb(dr-i-1);
			int elimhere=min(dr,k-1)-__builtin_popcount(b),elimbef=n-dr-2;
			int elim=elimhere+elimbef,rank=n-elim;
			int dif=min(k,pr-dr),ins=ntran[dif][b].size();
			//cout<<cpp<<' '<<pr<<' '<<dr<<' '<<b<<en;
			for (int ndr=0;ndr<ins;++ndr)
			{
				an[in[ndr]]+=rank*cpp*nprob[dif][b][ndr];
				if (rank>2)
				{
					int nnpr=pr-ntran[dif][b][ndr].x.x,nndr=dr-ntran[dif][b][ndr].x.y;
					int nb=ntran[dif][b][ndr].y;
					if (nndr<k-1)
					{
						nb&=(1<<nndr)-1;
					}
					//cout<<"MAK "<<in[ndr]<<": "<<nnpr<<' '<<nndr<<' '<<nb<<en;
					dp[ind[nndr][nnpr]][nb]+=cpp*nprob[dif][b][ndr];
				}
				else
				{
					assert(ins==2);
					an[in[1-ndr]]+=cpp*nprob[dif][b][ndr];
				}
			}
			
			//cout<<cpp<<en;
		}
		vector<double> gem=getMal();
		for (int i=0;i<k;++i) an[i]=gem[i];
		for (int i=k;i<=n-100;++i) an[i]=i+2;
	}
	cout<<fixed<<setprecision(10);
	double s=0;
	for (int i=0;i<n;++i) cout<<an[i]<<en,s+=an[i];
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4568kb

input:

3 2

output:

2.1093750000
2.6250000000
1.2656250000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 7273ms
memory: 443300kb

input:

1000 10

output:

2.9272933166
3.5373161569
4.2811822033
5.1312206602
6.0539327790
7.0191885099
8.0057023991
9.0012910303
10.0001652077
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 503ms
memory: 174900kb

input:

300 8

output:

2.7512630513
3.3900737271
4.1750068651
5.0660215194
6.0201465578
7.0045578589
8.0005725931
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 300 numbers

Test #4:

score: 0
Accepted
time: 16ms
memory: 135220kb

input:

1000 3

output:

2.2302561681
3.0347656711
4.0000000000
5.0000000000
6.0000000000
7.0000000000
8.0000000000
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 1123ms
memory: 5296kb

input:

7 10

output:

2.9815864384
3.4936049601
3.9653422649
4.3196770586
4.5087248562
4.4988808477
4.2321835741

result:

ok 7 numbers

Test #6:

score: 0
Accepted
time: 2916ms
memory: 436240kb

input:

993 9

output:

2.8411212285
3.4643592446
4.2273243674
5.0969425982
6.0352816658
7.0105742428
8.0023873942
9.0003025184
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
23.0000000000
...

result:

ok 993 numbers
English 繁體中文 简体中文

伺服器時間: 2024-12-02 18:05:08 | 開源專案