Submission #292938

#	Time	Username	Problem	Language	Result	Execution time	Memory
292938		arnold518	Spring cleaning (CEOI20_cleaning)	C++14	0 / 100	1062 ms	262148 KiB

cleaning

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

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

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

int R, C, Q;
pll dp1[MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10], dp3[MAXN+10][MAXN+10];

typedef vector<vector<ll>> Mat;

Mat operator * (const Mat &p, const Mat &q)
{
	Mat ret=vector<vector<ll>>(p.size(), vector<ll>(q[0].size()));
	assert(p[0].size()==q.size());
	for(int i=0; i<p.size(); i++) for(int j=0; j<q[0].size(); j++)
	{
		for(int k=0; k<q.size(); k++)
		{
			ret[i][j]+=p[i][k]*q[k][j]%MOD;
			ret[i][j]%=MOD;
		}
	}
	return ret;
}

Mat Matpow(Mat x, ll y)
{
	if(y==1) return x;
	if(y%2) return x*Matpow(x, y-1);
	Mat t=Matpow(x, y/2);
	return t*t;
}

pll operator + (const pll &p, const pll &q)
{
	if(p.first==q.first) return {p.first, (p.second+q.second)%MOD};
	return min(p, q);
}

int main()
{
	scanf("%d%d%d", &R, &C, &Q);
	Mat p=vector<vector<ll>>(C, vector<ll>(C));
	for(int i=0; i<C; i++)
	{
		if(i!=0) p[i][i-1]=1;
		p[i][i]=1;
		if(i!=C-1) p[i][i+1]=1;
	}
	Mat q=p;
	bool flag=false;		

	while(Q--)
	{
		char c; int a, b;
		scanf(" %c%d%d", &c, &a, &b);
		if(c=='P')
		{
			if(a==b) printf("%d 1\n", R-1);
			else printf("0 0\n");
		}
		else if(c=='R')
		{
			if(a==b) printf("1 1\n");
			else printf("2 2\n");
		}
		else if(c=='Q')
		{
			if(a==b) printf("1 1\n");
			else if(abs(a-b)==R-1) printf("1 1\n");
			else
			{
				vector<pii> V;
				V.push_back({R, a-(R-1)});
				V.push_back({R, a});
				V.push_back({R, a+(R-1)});
				V.push_back({1, b-(R-1)});
				V.push_back({1, b});
				V.push_back({1, b+(R-1)});

				V.push_back({b+R-a, a});
				V.push_back({R-b+a, a});

				if((R-b+a+1)%2==0) V.push_back({(R-b+a+1)/2, (a+1-R+b)/2});
				V.push_back({a+1-b, b});

				V.push_back({1-a+b, b});
				if((b+R+1-a)%2==0) V.push_back({(b+R+1-a)/2, (b+R-1+a)/2});

				int ans=0;
				for(auto it : V) if(1<=it.first && it.first<=R && 1<=it.second && it.second<=C) ans++;
				printf("2 %d\n", ans);
			}
		}
		else if(c=='B')
		{
			if((a+1)%2!=(b+R)%2) printf("0 0\n");
			else if(abs(a-b)==R-1) printf("1 1\n");
			else
			{
				int lo=1, hi=1e9;
				while(lo+1<hi)
				{
					int mid=lo+hi>>1;
					bool flag=false;
					if(mid%2==0)
					{
						if(2-a+(ll)(C-1)*mid>=b+R) flag=true;
						if(a-1+(ll)(mid-2)*(C-1)>=R-b) flag=true;
					}
					else
					{
						if(a-C+(ll)mid*(C-1)>=b+R) flag=true;	
						if(1-a+(ll)(mid-2)*(C-1)>=R-b) flag=true;
					}
					if(flag) hi=mid;
					else lo=mid;
				}

				for(int i=1; i<=C; i++)
				{
					dp1[1][i]={987654321, 0};
					dp2[1][i]={987654321, 0};
					dp3[1][i]={987654321, 0};
				}
				dp1[1][a]={0, 1};
				dp2[1][a]={0, 1};
				dp3[1][a]={0, 1};

				for(int i=2; i<=R; i++)
				{
					for(int j=1; j<=C; j++)
					{
						dp1[i][j]={987654321, 0};
						if(j!=1) dp1[i][j]=dp1[i][j]+pll(dp2[i-1][j-1].first+1, dp2[i-1][j-1].second);
						if(j!=C) dp1[i][j]=dp1[i][j]+pll(dp3[i-1][j+1].first+1, dp3[i-1][j+1].second);
						dp2[i][j]=dp3[i][j]=dp1[i][j];
						if(j!=1) dp2[i][j]=dp2[i][j]+dp2[i-1][j-1];
						if(j!=C) dp3[i][j]=dp3[i][j]+dp3[i-1][j+1];
						printf("%3lld ", dp1[i][j].second);
					}
					printf("\n");
				}
				printf("%lld %lld\n", dp1[R][b].first, dp1[R][b].second);
			}
		}
		else
		{
			if(!flag)
			{
				flag=true;
				p=Matpow(p, R-1);
			}
			printf("%d %lld\n", R-1, p[a-1][b-1]);
		}
	}
}

Compilation message (stderr)

cleaning.cpp: In function 'Mat operator*(const Mat&, const Mat&)':
cleaning.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<p.size(); i++) for(int j=0; j<q[0].size(); j++)
      |               ~^~~~~~~~~
cleaning.cpp:20:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<p.size(); i++) for(int j=0; j<q[0].size(); j++)
      |                                             ~^~~~~~~~~~~~
cleaning.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int k=0; k<q.size(); k++)
      |                ~^~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:109:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |      int mid=lo+hi>>1;
      |              ~~^~~
cleaning.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%d%d", &R, &C, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf(" %c%d%d", &c, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30