oj.uz

답안 #578194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578194 2022-06-16T07:36:55 Z amunduzbaev Chess Rush (CEOI20_chessrush) C++17
23 / 100
 12 ms 464 KB 
#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++){
		if(d[n][j]) d[n][j]--;
		res[i][j] = {d[n][j], 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;
	if(n <= 100){
		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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Runtime error 1 ms 464 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -