Submission #578198

#	Time	Username	Problem	Language	Result	Execution time	Memory
578198		amunduzbaev	Chess Rush (CEOI20_chessrush)	C++17	15 / 100	70 ms	616 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;
//~ }

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++){
		if(d[n][j]) d[n][j]--;
		res[i][j] = {d[n][j], cnt[n][j]};
	}
}

struct mtx{
	int n;
	vector<vector<int>> m;
	mtx (int n) : n(n){
		m.resize(n);
		for(auto& x : m) x.resize(n);
	}
	
	mtx operator * (mtx& b){
		mtx c(n);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					c.m[i][j] = (c.m[i][j] + m[i][k] * 1ll * b.m[k][j]) % mod;
				}
			}
		}
		
		return c;
	}
};

mtx bp(mtx a, int b){
	mtx c(N);
	for(int i=0;i<N;i++) c.m[i][i] = 1;
	while(b){
		if(b & 1) c = c * a;
		a = a * a, b >>= 1;
	} return c;
}

void King(int i, int j){
	
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int q; cin>>n>>m>>q;
	if(n <= 100){
		for(int i=1;i<=m;i++){
			Bishop(i);
		}
	}
	mtx a(N);
	
	if(m <= 100){
		for(int i=1;i<=n;i++){
			a.m[i][i] = 1;
			if(i > 1) a.m[i][i-1] = 1;
			if(i < n) a.m[i][i+1] = 1;
		}
		
		a = bp(a, n - 1);
	}
	
	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'){
			cout<<n - 1<<" "<<a.m[i][j]<<"\n";
		} if(c == 'B'){
			cout<<res[i][j][0]<<" "<<res[i][j][1]<<"\n";
		}
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 15 / 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