QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110911 | #6565. Game Show Elimination | He_Ren | WA | 508ms | 68792kb | C++17 | 4.3kb | 2023-06-04 18:09:10 | 2023-06-04 18:09:11 |
Judging History
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'