oj.uz

Submission #365171

# Submission time Handle Problem Language Result Execution time Memory
365171 2021-02-11T06:05:02 Z arnold518 None (JOI16_solitaire) C++14
12 / 100
 6 ms 768 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Incorrect 3 ms 748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 4 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 4 ms 748 KB Output is correct
12 Correct 4 ms 748 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 3 ms 748 KB Output is correct
15 Correct 3 ms 752 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 3 ms 748 KB Output is correct
18 Correct 3 ms 748 KB Output is correct
19 Correct 3 ms 748 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 3 ms 748 KB Output is correct
22 Correct 4 ms 768 KB Output is correct
23 Correct 4 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 748 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Incorrect 3 ms 748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Incorrect 3 ms 748 KB Output isn't correct
5 Halted 0 ms 0 KB -