Submission #365171

#	Time	Username	Problem	Language	Result	Execution time	Memory
365171		arnold518	Solitaire (JOI16_solitaire)	C++14	12 / 100	6 ms	768 KiB

solitaire

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 6000;
const ll MOD = 1e9+7;

int N, cnt;
char S[4][MAXN+10];
int A[4][MAXN+10];
ll fac[MAXN+10], ifac[MAXN+10];

vector<int> V[MAXN+10];
vector<int> adj[MAXN+10];
ll ans;

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll t=mypow(x, y/2);
	return t*t%MOD;
}

ll inv(ll x)
{
	return mypow(x, MOD-2);
}

bool vis[MAXN+10];

bool chk[MAXN+10];
bool f(vector<int> VV)
{
	for(auto it : VV) chk[it]=0;
	for(auto it : VV)
	{
		if(V[it].empty())
		{
			chk[it]=true;
			continue;
		}
		bool flag=false;
		for(auto jt : V[it])
		{
			if(chk[jt]) flag=true;
		}
		if(!flag) return false;
		chk[it]=true;
	}
	return true;
}

int main()
{
	fac[0]=1; ifac[0]=1;
	for(int i=1; i<=MAXN; i++) fac[i]=fac[i-1]*i%MOD;
	for(int i=1; i<=MAXN; i++) ifac[i]=inv(fac[i]);

	scanf("%d", &N);
	scanf(" %s", S[1]+1);
	scanf(" %s", S[2]+1);
	scanf(" %s", S[3]+1);
	for(int i=1; i<=N; i++)
	{
		A[1][i]=(S[1][i]=='x');
		A[2][i]=(S[2][i]=='x');
		A[3][i]=(S[3][i]=='x');
	}

	A[1][0]=1; A[1][N+1]=1;
	A[2][0]=1; A[2][N+1]=1;
	A[3][0]=1; A[3][N+1]=1;
	for(int i=1; i<=N; i++)
	{
		if(A[1][i])
		{
			if(A[1][i-1] || A[1][i+1])
			{
				return !printf("0\n");
			}
		}
	}
	for(int i=1; i<=N; i++)
	{
		if(A[3][i])
		{
			if(A[3][i-1] || A[3][i+1])
			{
				return !printf("0\n");
			}
		}
	}

	for(int i=1; i<=3; i++) for(int j=1; j<=N; j++) if(A[i][j]) cnt++;

	for(int i=1; i<=N; i++) if(A[1][i]) A[1][i]++;
	for(int i=1; i<=N; i++) if(A[3][i]) A[3][i]++;

	for(int i=1; i<=N; i++)
	{
		if(A[2][i]==0) continue;
		if(A[1][i]==0 && A[3][i]==0) A[2][i]=2;
		if(A[2][i-1]==0 && A[2][i+1]==0) A[2][i]=2;

		if(A[2][i]==1)
		{
			if(A[1][i])
			{
				V[i+N].push_back(i);
				adj[i+N].push_back(i);
				adj[i].push_back(i+N);
			}
			if(A[3][i])
			{
				V[i+N].push_back(i+N+N);
				adj[i+N].push_back(i+N+N);
				adj[i+N+N].push_back(i+N);
			}
			if(A[2][i-1])
			{
				V[i+N].push_back(i+N-1);
				adj[i+N].push_back(i+N-1);
				adj[i+N-1].push_back(i+N);
			}
			if(A[2][i+1])
			{
				V[i+N].push_back(i+N+1);
				adj[i+N].push_back(i+N+1);
				adj[i+N+1].push_back(i+N);
			}
		}
	}

	ans=fac[cnt];
	for(int i=1; i<=N; i++)
	{
		if(A[2][i]==0) continue;
		if(vis[i+N]) continue;

		vector<int> VV;
		queue<int> Q;
		vis[i+N]=1;
		Q.push(i+N);
		while(!Q.empty())
		{
			int now=Q.front(); Q.pop();
			VV.push_back(now);
			for(auto nxt : adj[now])
			{
				if(vis[nxt]) continue;
				vis[nxt]=true;
				Q.push(nxt);
			}
		}
		ans=ans*ifac[VV.size()]%MOD;

		int t=0;
		sort(VV.begin(), VV.end());
		do
		{
			t+=f(VV);
		}while(next_permutation(VV.begin(), VV.end()));
		//for(auto it : VV) printf("%d ", it); printf(" : %d\n", t);
		ans=ans*t%MOD;
	}	
	printf("%lld\n", ans);
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
solitaire.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf(" %s", S[1]+1);
      |  ~~~~~^~~~~~~~~~~~~~~
solitaire.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf(" %s", S[2]+1);
      |  ~~~~~^~~~~~~~~~~~~~~
solitaire.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf(" %s", S[3]+1);
      |  ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 20
• Subtask 4: 0 / 38
• Subtask 5: 0 / 20