QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278989#6565. Game Show Eliminationucup-team191TL 1ms6664kbC++236.7kb2023-12-08 00:33:162023-12-08 00:33:16

Judging History

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

  • [2023-12-08 00:33:16]
  • 评测
  • 测评结果：TL
  • 用时：1ms
  • 内存：6664kb
查看
  • [2023-12-08 00:33:16]
  • 提交

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=602,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()
{
	int starn=n;
	n=100;
	broj.clear();
	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 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)
	{
		dp[ind[dr][pr]][b]=0;
	}
	dp[ind[n-2][n-1]][(1<<min(n-2,k-1))-1]=1;
	vector<double> mojan(n);
	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-30) 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)
		{
			mojan[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);
				mojan[in[1-ndr]]+=cpp*nprob[dif][b][ndr];
			}
		}
		
		//cout<<cpp<<en;
	}
	vector<double> re(k);
	for (int i=0;i<k;++i) re[i]=mojan[i];
	n=starn;
	return re;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	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=150,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-30) 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-145;++i) an[i]=i+1;
	}
	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: 6664kb

input:

3 2

output:

2.1093750000
2.6250000000
1.2656250000

result:

ok 3 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

1000 10

output:

996 998 1000
993 997 2000
989 996 3000
984 995 4000
978 994 5000
971 993 6000
963 992 7000
954 991 8000
944 990 9000
933 989 10000
921 988 11000
908 987 12000
894 986 13000
879 985 14000
863 984 15000
846 983 16000
828 982 17000
809 981 18000
789 980 19000
768 979 20000
746 978 21000
723 977 22000
6...

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:41:57 | 开源项目