QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #278937 | #6565. Game Show Elimination | ucup-team191# | RE | 0ms | 6448kb | C++14 | 6.5kb | 2023-12-07 23:14:30 | 2023-12-07 23:14:31 |
Judging History
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[N];
int ind[N][N];
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;
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)
{
dp[ind[dr][pr]][b]=0;
}
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=i+1;j<n;++j)
{
ind[i][j]=broj.size();
broj.pb({i,j});
}
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;
double su=0;
//cout<<dif<<' '<<b<<en;
//for (auto x: novp) cout<<x<<' ',su+=x;
//cout<<su<<en;
}
//cout<<en;
if (n<=400)
{
int csta=0;
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
{
int csta=0;
dp[ind[n-2][n-1]][(1<<min(n-2,k-1))-1]=1;
for (int pr=n-1;pr>=n-350;--pr) for (int dr=pr-1;dr>=n-350;--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)
{
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-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];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6448kb
input:
3 2
output:
2.1093750000 2.6250000000 1.2656250000
result:
ok 3 numbers
Test #2:
score: -100
Runtime Error
input:
1000 10