QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #278989 | #6565. Game Show Elimination | ucup-team191 | TL | 1ms | 6664kb | C++23 | 6.7kb | 2023-12-08 00:33:16 | 2023-12-08 00:33:16 |
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=602,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;
broj.clear();
for (int i=n-1;i>=0;--i) for (int j=i-1;j>=0;--j)
{
ind[j][i]=broj.size();
broj.pb({j,i});
}
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=n-1;i>=0;--i) for (int j=i-1;j>=0;--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=150,MAX=n-U;
dp[ind[n-2][n-1]][(1<<min(n-2,k-1))-1]=1;
int maind=0;
for (int pr=n-1;pr>=MAX;--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 (ind[dr][pr]>maind)
{
maind=ind[dr][pr];
if (maind%1000==0) cout<<dr<<' '<<pr<<' '<<ind[dr][pr]<<endl;
}
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-145;++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: 1ms
memory: 6664kb
input:
3 2
output:
2.1093750000 2.6250000000 1.2656250000
result:
ok 3 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
1000 10
output:
996 998 1000 993 997 2000 989 996 3000 984 995 4000 978 994 5000 971 993 6000 963 992 7000 954 991 8000 944 990 9000 933 989 10000 921 988 11000 908 987 12000 894 986 13000 879 985 14000 863 984 15000 846 983 16000 828 982 17000 809 981 18000 789 980 19000 768 979 20000 746 978 21000 723 977 22000 6...