oj.uz

Submission #578200

# Submission time Handle Problem Language Result Execution time Memory
578200 2022-06-16T07:47:56 Z amunduzbaev Chess Rush (CEOI20_chessrush) C++17
51 / 100
 316 ms 760 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;
//~ }

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<=m;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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 596 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 596 KB Output is correct
2 Correct 166 ms 468 KB Output is correct
3 Correct 21 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 596 KB Output is correct
2 Correct 65 ms 596 KB Output is correct
3 Correct 59 ms 596 KB Output is correct
4 Correct 61 ms 596 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 596 KB Output is correct
2 Correct 65 ms 596 KB Output is correct
3 Correct 59 ms 596 KB Output is correct
4 Correct 61 ms 596 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 600 KB Output is correct
2 Correct 177 ms 616 KB Output is correct
3 Correct 149 ms 556 KB Output is correct
4 Correct 52 ms 600 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 600 KB Output is correct
2 Correct 177 ms 616 KB Output is correct
3 Correct 149 ms 556 KB Output is correct
4 Correct 52 ms 600 KB Output is correct
5 Correct 72 ms 596 KB Output is correct
6 Correct 59 ms 624 KB Output is correct
7 Correct 140 ms 760 KB Output is correct
8 Correct 149 ms 680 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 600 KB Output is correct
2 Correct 177 ms 616 KB Output is correct
3 Correct 149 ms 556 KB Output is correct
4 Correct 52 ms 600 KB Output is correct
5 Correct 72 ms 596 KB Output is correct
6 Correct 59 ms 624 KB Output is correct
7 Correct 140 ms 760 KB Output is correct
8 Correct 149 ms 680 KB Output is correct
9 Correct 179 ms 468 KB Output is correct
10 Correct 299 ms 508 KB Output is correct
11 Correct 316 ms 468 KB Output is correct
12 Correct 265 ms 504 KB Output is correct
13 Correct 222 ms 500 KB Output is correct
14 Correct 241 ms 492 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 600 KB Output is correct
2 Correct 177 ms 616 KB Output is correct
3 Correct 149 ms 556 KB Output is correct
4 Correct 52 ms 600 KB Output is correct
5 Correct 72 ms 596 KB Output is correct
6 Correct 59 ms 624 KB Output is correct
7 Correct 140 ms 760 KB Output is correct
8 Correct 149 ms 680 KB Output is correct
9 Correct 179 ms 468 KB Output is correct
10 Correct 299 ms 508 KB Output is correct
11 Correct 316 ms 468 KB Output is correct
12 Correct 265 ms 504 KB Output is correct
13 Correct 222 ms 500 KB Output is correct
14 Correct 241 ms 492 KB Output is correct
15 Correct 245 ms 500 KB Output is correct
16 Correct 240 ms 504 KB Output is correct
17 Runtime error 1 ms 468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 596 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -