Submission #212437

#	Time	Username	Problem	Language	Result	Execution time	Memory
212437		zscoder	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	868 ms	512 KiB

ruins3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = (1e9 + 7);
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
void radd(int &a, int b)
{
	a=add(a,b); 
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
	a=mult(a,b);
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}
	
int ways[2222];

int p2(int x)
{
	if(x>=0) return pow2[x];
	else return inverse(pow2[-x]);
}

int ok[2222];
int precalc[2222][2222];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(2222);
	int n; cin>>n;
	/*
	ways[1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			int S=i-j;
			int ones=(j==1);
			int ans=0;
			if(S==0) ans=p2(i-2);
			else
			{
				for(int k=1;k<=S;k++)
				{
					int res=0;
					for(int l=-1;l<=k-1;l++)
					{
						if(l==-1)
						{
							if(S-k==0) res=add(res,pow2[2*(k-1-l)]);
						}
						else res=add(res,mult(pow2[2*(k-1-l)],choose(S-k-1,l)));
					}
					ans=add(ans,mult(res,p2(i-2*(k+1))));
				}
			}
			ans=mult(ans,j);
			ans=mult(ans,p2(ones*2));
			cerr<<i<<' '<<j<<' '<<ans<<'\n';
			radd(ways[i],ans);
		}
		ways[i]=mult(ways[i],fact[i-1]);
		cerr<<i<<' '<<ways[i]<<'\n';
	}
	*/
	/*
	precalc[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			if(j+2<=n) radd(precalc[i+1][j+2],precalc[i][j]);
			if(j+1<=n) radd(precalc[i+1][j+1],mult(2,precalc[i][j]));
			radd(precalc[i+1][j],precalc[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		ways[i]=precalc[i-1][i-1];
		ways[i]=mult(ways[i],mult(fact[i-1],i+1));
	}
	*/
	for(int i=1;i<=n;i++)
	{
		ways[i]=mult(choose(2*i,i),fact[i-1]);
	}
	for(int i=0;i<n;i++)
	{
		int x; cin>>x; x--;
		ok[x]=1;
	}
	vi old(n+1,0);
	old[0]=1;
	int surv=0;
	int ded=0;
	for(int i=2*n-1;i>=0;i--)
	{
		vi nw(n+1,0);
		if(ok[i])
		{
			for(int j=ded;j<=surv;j++)
			{
				radd(nw[j],old[j]);
				for(int k=j+1;k<=surv+1;k++)
				{
					//most recent one must be chosen, so k-j-1 slots left
					radd(nw[k],mult(old[j],mult(choose(surv-j,k-j-1),ways[k-j])));
				}
			}
		}
		else
		{
			for(int j=ded;j<=surv;j++)
			{
				radd(nw[j],mult(old[j],j-ded));
			}
		}
		if(ok[i]) surv++;
		else ded++;
		old=nw;
	}
	cout<<mult(old[n],p2(-n))<<'\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42