QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110911#6565. Game Show EliminationHe_RenWA 508ms68792kbC++174.3kb2023-06-04 18:09:102023-06-04 18:09:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-04 18:09:11]
  • 评测
  • 测评结果:WA
  • 用时:508ms
  • 内存:68792kb
  • [2023-06-04 18:09:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ldb;
typedef pair<int,int> pii;
const int MAXN = 1000 + 5;
const int MAXD = 10 + 5;
const int ALL = (1<<10) + 5;
const ldb eps = 1e-9;

inline int sgn(ldb x){ return x<-eps? -1: x>eps? 1: 0;}

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)

using Poly = vector<ldb>;

Poly& operator += (Poly &A,const Poly &B)
{
	if(A.size() < B.size()) A.resize(B.size());
	for(int i=0; i<(int)B.size(); ++i)
		A[i] += B[i];
	return A;
}
Poly mul(Poly A,ldb k,ldb b)
{
	Poly res(A.size() + 1);
	for(int i=0; i<(int)A.size(); ++i)
	{
		res[i+1] += A[i] * k;
		res[i] += A[i] * b;
	}
	return res;
}

int n,d;

ldb getprob(vector<int> vec,int x)
{
	ldb res = 0;
	for(int k=0; k<d; ++k)
	{
		vector<Poly> f(2);
		f[0] = {(ldb)1 / d};
		for(int y: vec)
		{
			if(y == x) continue;
			if(y+d <= x+k) continue;
			
			if(y >= x+k+1)
			{
				f[1] = f[0];
				f[0] = {};
				continue;
			}
			
			vector<Poly> nf(2);
			nf[0] += mul(f[0], (ldb)1 / d, (ldb)-y / d);
			nf[1] += mul(f[1], (ldb)1 / d, (ldb)-y / d);
			nf[1] += mul(f[0], (ldb)-1 / d, (ldb)(y+d) / d);
			f = nf;
		}
		
		ldb l = 1, r = 1;
		for(int i=0; i<(int)f[1].size(); ++i)
		{
			l *= x+k;
			r *= x+k+1;
			res += (r - l) * f[1][i] / (i+1);
		}
	}
	
//	printf("vec: ");
//	for(auto t: vec)
//		printf("%d ",t);
//	printf("\n");
//	printf("x = %d\n",x);
//	printf("prob = %lf\n",res);
	
	return res;
}

tuple<int,int,int> getnxt(int i,int mask,int fir,int j)
{
	vector<int> vec = {i + fir, i};
	for(int k=1; k<=2*d; ++k) if(k>d-1 || bdig(mask, k-1))
		vec.emplace_back(i - k);
	vec.erase(find(vec.begin(), vec.end(), j));
	
	int nxt = 0;
	for(int t: vec)
		if(vec[1]-d < t && t < vec[1])
			nxt |= bbit(vec[1] - t - 1);
	
	return make_tuple(vec[1], nxt, vec[0] - vec[1]);
}

int main(void)
{
	scanf("%d%d",&n,&d);
	
	int all = (1<<(d-1))-1;
	
	static vector< tuple<int,int,int,ldb,int> > trans[ALL][MAXD];
	
	for(int mask=0; mask<=all; ++mask)
		for(int fir=1; fir<=d; ++fir)
		{
			int i = 10 * d;
			
			vector<int> vec = {i + fir, i};
			for(int k=1; k<=d-1; ++k) if(bdig(mask, k-1))
				vec.emplace_back(i - k);
			
			for(int t: vec)
			{
				ldb coef = getprob(vec, t);
				
				auto to = getnxt(i, mask, fir, t);
				get<0>(to) -= i;
				
				trans[mask][fir].emplace_back(tuple_cat(to, make_tuple(coef, t - i)));
			}
		}
	
	static ldb dp[MAXN][ALL][MAXD];
	static ldb ans[MAXN];
	
	dp[n-1][all][1] = 1;
	for(int i=n-1; i>=0; --i)
		for(int mask=all; mask>=0; --mask)
			for(int fir=d; fir>=1; --fir)
			{
				ldb cur = dp[i][mask][fir];
				if(sgn(cur) <= 0) continue;
				
//				printf("\n");
//				printf("dp[%d][%d][%d] = %lf\n",i,mask,fir,cur);
				
				int rem = 0;
				rem += n-i-1;
				rem += d-1 - (int)__builtin_popcount(mask);
				rem = n - rem;
				
//				printf("rem = %d\n",rem);
				
				if(i-2*d >= 0)
				{
					for(auto t: trans[mask][fir])
					{
						int ni = i + get<0>(t);
						int nmask = get<1>(t);
						int nfir = get<2>(t);
						ldb nxt = cur * get<3>(t);
						
						if(nfir > d)
						{
							ans[ni+nfir] += nxt;
							ans[ni+d] -= nxt;
							nfir = d;
						}
						
						int k = i + get<4>(t);
						ans[k] += nxt * rem;
						
						dp[ni][nmask][nfir] += nxt;
					}
					continue;
				}
				
				if(i == 0)
				{
					ans[fir] += cur;
					continue;
				}
				
				vector<int> vec = {i + fir, i};
				for(int k=1; k<=d-1; ++k) if(i - k >= 1 && bdig(mask, k-1))
					vec.emplace_back(i - k);
				
//				printf("\n");
//				printf("vec: ");
//				for(auto t: vec)
//					printf("%d ",t);
//				printf("\n");
				
				for(int k: vec)
				{
					ldb coef = getprob(vec, k);
//					printf("del %d, prob = %lf\n",k,coef);
					
					auto t = getnxt(i, mask, fir, k);
					
					int ni = get<0>(t);
					int nmask = get<1>(t);
					int nfir = get<2>(t);
					ldb nxt = cur * coef;
					
					if(nfir > d)
					{
						ans[ni+nfir] += nxt;
						ans[ni+d] -= nxt;
						nfir = d;
					}
					
					ans[k] += nxt * rem;
					
//					printf("to %d %d %d\n",ni,nmask,nfir);
//					printf("ans[%d] += %lf * %d\n",k,nxt,rem);
					
					dp[ni][nmask][nfir] += nxt;
				}
			}
	
	for(int i=1; i<=n; ++i)
		printf("%.15lf\n",(double)ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4020kb

input:

3 2

output:

2.109375000000000
2.625000000000000
1.265625000000000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 508ms
memory: 68792kb

input:

1000 10

output:

2.894005080571093
3.497090990268490
4.232498095261995
5.072870270369721
5.985089696996709
6.939368981889396
7.914664752210904
8.898932229610777
9.886448182480699
10.874914276689367
11.863537413654553
12.852152152107507
13.840776472218273
14.829399074118205
15.818025773022191
16.806658549193639
17.79...

result:

wrong answer 1st numbers differ - expected: '2.9272933', found: '2.8940051', error = '0.0113717'