QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111039 | #6565. Game Show Elimination | He_Ren | AC ✓ | 3004ms | 128868kb | C++17 | 4.5kb | 2023-06-05 16:49:05 | 2023-06-05 16:49:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long 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-12;
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)
{
if(!sgn(f[1][i])) continue;
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<=2*d; ++k) if(k > d-1 || bdig(mask, k-1))
vec.emplace_back(i - k);
for(int t: vec)
{
ldb coef = getprob(vec, t);
if(!sgn(coef)) continue;
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 >= 1)
{
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<=2*d; ++k) if(i - k >= 1 && (k > d-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);
if(!sgn(coef)) continue;
// 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: 4012kb
input:
3 2
output:
2.109375000000000 2.625000000000000 1.265625000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 3004ms
memory: 128868kb
input:
1000 10
output:
2.927293815167034 3.537316759339912 4.281182932480037 5.131221534154514 6.053933810161562 7.019189705439029 8.005703762736966 9.001292563577303 10.000166911078047 11.000001873758144 12.000002044190177 13.000002214010852 14.000002383330358 15.000002554401989 16.000002724417811 17.000002894599088 18.0...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 308ms
memory: 16264kb
input:
300 8
output:
2.751263041338706 3.390073714740936 4.175006849914750 5.066021501039692 6.020146535973711 7.004557833455156 8.000572564004493 8.999999967308991 9.999999963676494 10.999999960047575 11.999999956413939 12.999999952781771 13.999999949152613 14.999999945518139 15.999999941884257 16.999999938252031 17.99...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 4ms
memory: 10736kb
input:
1000 3
output:
2.230256168087017 3.034765671091544 3.999999999971443 4.999999999964303 5.999999999957164 6.999999999950025 7.999999999942886 8.999999999935746 9.999999999928606 10.999999999921467 11.999999999914328 12.999999999907189 13.999999999900050 14.999999999892909 15.999999999885770 16.999999999878629 17.99...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 1905ms
memory: 8268kb
input:
7 10
output:
2.981586438371783 3.493604960118067 3.965342264912735 4.319677058587534 4.508724856222704 4.498880847650540 4.232183574136635
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 987ms
memory: 69412kb
input:
993 9
output:
2.841121465169590 3.464359533207531 4.227324719562990 5.096943022722247 6.035282168519746 7.010574826762612 8.002388060805151 9.000303268069178 10.000000832941870 11.000000916222541 12.000000999686995 13.000001083112338 14.000001166545635 15.000001249709054 16.000001332936428 17.000001416200512 18.0...
result:
ok 993 numbers