Submission #578186

#	Time	Username	Problem	Language	Result	Execution time	Memory
578186		amunduzbaev	Chess Rush (CEOI20_chessrush)	C++17	0 / 100	13 ms	596 KiB

chessrush

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int mod = 1e9 + 7;
int n, m;

void Pawn(int i, int j){
	if(i != j){
		cout<<0<<" "<<0<<"\n";
		return;
	}
	
	cout<<n - 1<<" "<<1<<"\n";
}

void Rook(int i, int j){
	if(i == j){
		cout<<1<<" "<<1<<"\n";
	} else {
		cout<<2<<" "<<2<<"\n";
	}
}

void Queen(int i, int j){
	ar<int, 2> d1 {}, d2 {};
	d1[0] = 1 + i, d2[0] = n + j;
	d1[1] = 1 - i, d2[1] = n - j;
	if(i == j || d1[0] == d2[0] || d1[1] == d2[1]){
		cout<<1<<" "<<1<<"\n";
		return;
	}
	
	cout<<2<<" ";
	int cnt = 2;
	if((d1[0] + d2[1]) % 2 == 0){
		int x = (d1[0] + d2[1]) / 2;
		int y = d1[0] - x;
		if(1 <= x && x <= n && 1 <= y && y <= m){
			cnt++;
		}
	}
	
	if((d1[1] + d2[0]) % 2 == 0){
		int x = (d1[1] + d2[0]) / 2;
		int y = d2[0] - x;
		if(1 <= x && x <= n && 1 <= y && y <= m){
			cnt++;
		}
	}
	
	{
		int y = j, x = d1[0] - y;
		if(1 <= x && x <= n){
			cnt += 2;
		}
		
		x = d1[1] + y;
		if(1 <= x && x <= n){
			cnt += 2;
		}
		
		x = n;
		y = d1[0] - x;
		if(1 <= y && y <= m){
			cnt++;
		}
		
		y = x - d1[1];
		if(1 <= y && y <= m){
			cnt++;
		}
		
		x = 1;
		y = d2[0] - x;
		if(1 <= y && y <= m){
			cnt++;
		}
		
		y = x - d2[1];
		if(1 <= y && y <= m){
			cnt++;
		}
	}
	
	cout<<cnt<<"\n";
}

int bp(int a, int b){
	int c = 1;
	while(b){
		if(b & 1) c = c * 1ll * a % mod;
		a = a * 1ll * a % mod, b >>= 1;
	} return c;
}

void King(int i, int j){
	int x = abs(i - j);
	int res = 1, inv = 1;
	for(int i = n; i < n + x; i++){
		res = (res * 1ll * i) % mod;
		inv = (inv * 1ll * (i - n + 1)) % mod;
	}
	
	cout<<n - 1<<" ";
	cout<<res * 1ll * bp(inv, mod - 2) % mod<<"\n";
}

const int N = 105;
int d[N][N], cnt[N][N];
ar<int, 2> res[N][N];

void Bishop(int i){
	memset(d, 0, sizeof d);
	memset(cnt, 0, sizeof cnt);
	d[1][i] = 1;
	cnt[1][i] = 1;
	queue<int> q;
	q.push(1 * N + i);
	while(!q.empty()){
		auto u = q.front(); q.pop();
		int i = u / N, j = u % N;
		for(int t=1;t<N;t++){
			int x = i + t, y = j - t;
			if(1 <= x && x <= n && 1 <= y && y <= m){
				if(d[x][y] == 0){
					d[x][y] = d[i][j] + 1;
					cnt[x][y] = cnt[i][j];
					q.push(x * N + y);
				} else if(d[x][y] == d[i][j] + 1){
					cnt[x][y] = (cnt[x][y] + cnt[i][j]) % mod;
				}
			}
			
			y = j + t;
			if(1 <= x && x <= n && 1 <= y && y <= m){
				if(d[x][y] == 0){
					d[x][y] = d[i][j] + 1;
					cnt[x][y] = cnt[i][j];
					q.push(x * N + y);
				} else if(d[x][y] == d[i][j] + 1){
					cnt[x][y] = (cnt[x][y] + cnt[i][j]) % mod;
				}
			}
		}
	}
	
	for(int j=1;j<=m;j++){
		res[i][j] = {d[n][j] - 1, cnt[n][j]};
	}
	//~ cout<<d[n][j]<<" "<<cnt[n][j]<<"\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int q; cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		Bishop(i);
	}
	while(q--){
		char c; cin>>c;
		int i, j; cin>>i>>j;
		if(c == 'P'){
			Pawn(i, j);
		} if(c == 'R'){
			Rook(i, j);
		} if(c == 'Q'){
			Queen(i, j);
		} if(c == 'K'){
			King(i, j);
		} if(c == 'B'){
			cout<<res[i][j][0]<<" "<<res[i][j][1]<<"\n";
		}
	}
}

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