Submission #291188

#	Time	Username	Problem	Language	Result	Execution time	Memory
291188		TadijaSebez	Chess Rush (CEOI20_chessrush)	C++11	100 / 100	421 ms	8696 KiB

chessrush

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
int r,c;
void P(int a,int b){
	if(a==b)printf("%i 1\n",r-1);
	else printf("0 0\n");
}
void R(int a,int b){
	if(a==b)printf("1 1\n");
	else printf("2 2\n");
}
void Q(int a,int b){
	if(a==b)printf("1 1\n");
	else if(a+1==b+r)printf("1 1\n");
	else if(a-1==b-r)printf("1 1\n");
	else{
		printf("2 ");
		int cnt=2;
		if(abs(a-b)<r)cnt+=2;
		if(a-r+1>0)cnt++;
		if(a+r-1<=c)cnt++;
		if(b-r+1>0)cnt++;
		if(b+r-1<=c)cnt++;
		int dif=(a-1)-(b-r);
		if(dif>0&&dif%2==0&&a-dif/2>0)cnt++;
		dif=(b+r)-(a+1);
		if(dif>0&&dif%2==0&&a+dif/2<=c)cnt++;
		printf("%i\n",cnt);
	}
}
#define ll long long
const int mod=1e9+7;
int mul(int x,int y){return (ll)x*y%mod;}
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;}
int pw(int x,int k){
	int ans=1;
	for(;k;k>>=1,x=mul(x,x))if(k&1)ans=mul(ans,x);
	return ans;
}
int inv(int x){return pw(x,mod-2);}
#define matrix vector<vector<int>>
int BigBinom(int n,int k){
	int ans=1;
	for(int i=1;i<=k;i++){
		ans=mul(ans,mul(n-i+1,inv(i)));
	}
	return ans;
}
pii SolveUp(int a,int b){
	if(a==1)return {mod,0};
	int n=1+(r-a)/(c-1);
	int ost=(r-a)%(c-1);
	int dir=n%2;
	int where=dir?ost+1:c-ost;
	if(ost>0)n++;
	if(where==b)return {n,1};
	if(ost==0)n++;
	int f;
	if(dir==0&&where<b)n++,f=(where+b)/2-1;
	else if(dir==0)f=(where-b)/2;
	if(dir==1&&where>b)n++,f=c+1-(where+b)/2-1;
	else if(dir==1)f=(b-where)/2;
	return {n,BigBinom(n+f-2,f)};
}
void B(int a,int b){
	if((a+1+b+r)%2!=0)printf("0 0\n");
	else if(a+r-1==b||a-r+1==b)printf("1 1\n");
	else{
		pii ans1=SolveUp(a,b);
		pii ans2=SolveUp(c-a+1,c-b+1);
		if(ans1.first>ans2.first)swap(ans1,ans2);
		if(ans1.first==ans2.first)ckadd(ans1.second,ans2.second);
		printf("%i %i\n",ans1.first,ans1.second);
	}
}
const int N=1050;
int dp[N][N],now[N][N];
void cl(){
	for(int i=1;i<=c;i++)
		for(int j=1;j<=c;j++)
			now[i][j]=0;
}
void upd(){
	for(int i=1;i<=c;i++)
		for(int j=1;j<=c;j++)
			dp[i][j]=now[i][j];
}
void BuildKing(){
	for(int i=1;i<=c;i++)dp[i][i]=1;
	for(int o=30;o>=0;o--){
		if((r-1)>>o&1){
			for(int i=1;i<=c;i++)
				for(int j=1;j<=c;j++)
					now[i][j]=add(dp[i][j],add(dp[i][j-1],dp[i][j+1]));
			upd();
		}
		if(o==0)break;
		cl();
		for(int i=1;i<=c;i++)
			for(int j=1;j<=c;j++)
				ckadd(now[1][i],mul(dp[1][j],dp[j][i]));
		for(int i=2;i<=c;i++){
			now[i][1]=now[1][i];
			for(int j=2;j<=c;j++){
				if(i+j<=c+1)now[i][j]=add(now[i-1][j-1],now[1][i+j-1]);
			}
		}
		for(int i=2;i<=c;i++)
			for(int j=2;j<=c;j++)
				if(i+j>c+1)now[i][j]=now[c+1-i][c+1-j];
		upd();
	}
}
void K(int a,int b){
	printf("%i %i\n",r-1,dp[a][b]);
}
int main(){
	int q;
	scanf("%i %i %i",&r,&c,&q);
	BuildKing();
	while(q--){
		char c;
		int a,b;
		scanf("\n%c %i %i",&c,&a,&b);
		if(c=='P')P(a,b);
		if(c=='R')R(a,b);
		if(c=='Q')Q(a,b);
		if(c=='B')B(a,b);
		if(c=='K')K(a,b);
	}
	return 0;
}

Compilation message (stderr)

chessrush.cpp: In function 'int main()':
chessrush.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |  scanf("%i %i %i",&r,&c,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
chessrush.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |   scanf("\n%c %i %i",&c,&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
chessrush.cpp: In function 'std::pair<int, int> SolveUp(int, int)':
chessrush.cpp:67:20: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  return {n,BigBinom(n+f-2,f)};
      |            ~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 22 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20
• Subtask 9: 7 / 7