#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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
19064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
164 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
170 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
