QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278982#6565. Game Show Eliminationucup-team191WA 5686ms261632kbC++236.5kb2023-12-08 00:19:122023-12-08 00:19:12

Judging History

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

  • [2023-12-08 00:19:12]
  • 评测
  • 测评结果：WA
  • 用时：5686ms
  • 内存：261632kb
查看
  • [2023-12-08 00:19:12]
  • 提交

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()
{
	int starn=n;
	n=100;
	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=0;i<n;++i) for (int j=0;j<i;++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=350,MAX=n-U;
		dp[ind[n-2-MAX][n-1-MAX]][(1<<min(n-2,k-1))-1]=1;
		for (int pr=n-1;pr>=MAX;--pr) for (int dr=pr-1;dr>=MAX;--dr) for (int b=(1<<min(dr,k-1))-1;b>=0;--b)
		{
			double cpp=dp[ind[dr-MAX][pr-MAX]][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)
			{
				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-MAX][nnpr-MAX]][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-300;++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: 4420kb

input:

3 2

output:

2.1093750000
2.6250000000
1.2656250000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 5686ms
memory: 261632kb

input:

1000 10

output:

2.9272923819
3.5373140623
4.2811782670
5.1312141813
6.0539231444
7.0191752280
8.0056850570
9.0012692121
10.0001384096
10.9999675541
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
...

result:

wrong answer 4th numbers differ - expected: '5.1312207', found: '5.1312142', error = '0.0000013'
English 繁體中文 简体中文

服务器时间: 2024-12-05 07:44:35 | 开源项目