Submission #163187

#	Time	Username	Problem	Language	Result	Execution time	Memory
163187		TadijaSebez	Solitaire (JOI16_solitaire)	C++11	100 / 100	112 ms	660 KiB

solitaire

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005;
const int M=3*N;
const int mod=1e9+7;
int mul(int x, int y){ return (ll)x*y%mod;}
void ckmul(int &x, int y){ x=mul(x,y);}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
void ckadd(int &x, int y){ x=add(x,y);}
int sub(int x, int y){ x-=y;return x<0?x+mod:x;}
void cksub(int &x, int y){ x=sub(x,y);}
int dp[2],dp_ok[2][M],dp_lo[2][M],dp_tmp[2][M],dp_pre[2][M];
char base[4][N];
void Clear(int col)
{
	dp[col]=0;
	for(int i=0;i<M;i++)
	{
		dp_ok[col][i]=0;
		dp_lo[col][i]=0;
		dp_tmp[col][i]=0;
		dp_pre[col][i]=0;
	}
}
int main()
{
	int n;
	scanf("%i",&n);
	scanf("%s %s %s",base[1]+1,base[2]+1,base[3]+1);
	for(int i=2;i<=n;i++) if(base[1][i]=='x' && base[1][i-1]=='x') return 0*printf("0\n");
	for(int i=2;i<=n;i++) if(base[3][i]=='x' && base[3][i-1]=='x') return 0*printf("0\n");
	int col=0,SZ=0;
	dp[col]=1;
	for(int i=1;i<=n+1;i++)
	{
		col^=1;
		Clear(col);
		if(base[2][i]=='x')
		{
			if(base[2][i-1]=='x')
			{
				for(int X=SZ+1;X>=1;X--)
				{
					if(X>SZ) dp_tmp[col][X]=0;
					else dp_tmp[col][X]=add(dp_tmp[col][X+1],dp_lo[col^1][X]);
				}
				int sum=0;
				for(int X=1;X<=SZ;X++) ckadd(sum,dp_ok[col^1][X]);
				for(int X=1;X<=SZ+1;X++) ckadd(dp_tmp[col][X],sum);
				for(int X=1;X<=SZ+1;X++)
				{
					dp_pre[col][X]=0;
					if(X>1) ckadd(dp_pre[col][X],add(dp_pre[col][X-1],dp_ok[col^1][X-1]));
				}
			}
			else
			{
				for(int X=SZ+1;X>=1;X--)
				{
					dp_tmp[col][X]=dp_pre[col][X]=dp[col^1];
				}
			}
			SZ++;
			int cs=(base[1][i]=='x')+(base[3][i]=='x');
			SZ+=cs;

			if(cs==0) for(int X=1;X<=SZ;X++) dp_ok[col][X]=dp_tmp[col][X];
			if(cs==1) for(int X=2;X<=SZ;X++) dp_ok[col][X]=mul(dp_tmp[col][X-1],X-1);
			if(cs==2) for(int X=3;X<=SZ;X++) dp_ok[col][X]=mul(dp_tmp[col][X-2],mul(X-1,X-2));

			//if(cs==0) for(int X=1;X<=SZ;X++) dp_lo[col][X]=dp_pre[col][X];
			if(cs==1) for(int X=1;X<=SZ;X++) dp_lo[col][X]=mul(dp_pre[col][X],SZ-X);
			if(cs==2) for(int X=1;X<=SZ;X++) dp_lo[col][X]=add(mul(dp_pre[col][X],mul(SZ-X,SZ-X-1)),mul(dp_pre[col][X-1],mul(mul(X-1,SZ-X),2)));
		}
		else
		{
			if(base[2][i-1]=='x')
			{
				for(int X=1;X<=SZ;X++) ckadd(dp[col],add(dp_ok[col^1][X],dp_lo[col^1][X]));
			}
			else
			{
				dp[col]=dp[col^1];
			}
			int cs=(base[1][i]=='x')+(base[3][i]=='x');
			SZ+=cs;
			if(cs==1) ckmul(dp[col],SZ);
			if(cs==2) ckmul(dp[col],mul(SZ,SZ-1));
		}

		/*printf("col:%i\n\n",i);
		if(base[2][i]=='x')
		{
			printf("dp_tmp:");for(int X=1;X<=SZ;X++) printf("%i ",dp_tmp[col][X]);printf("\n");
			printf("dp_pre:");for(int X=1;X<=SZ;X++) printf("%i ",dp_pre[col][X]);printf("\n");
			printf("dp_lo:");for(int X=1;X<=SZ;X++) printf("%i ",dp_lo[col][X]);printf("\n");
			printf("dp_ok:");for(int X=1;X<=SZ;X++) printf("%i ",dp_ok[col][X]);printf("\n");
		}
		else
		{
			printf("dp: %i\n",dp[col]);
		}
		printf("\n");*/
	}
	printf("%i\n",dp[col]);
	return 0;
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
solitaire.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s %s %s",base[1]+1,base[2]+1,base[3]+1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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