Submission #1218199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218199		damamila	Chess Rush (CEOI20_chessrush)	C++20	48 / 100	1187 ms	131032 KiB

chessrush

#include <bits/stdc++.h>
#include "arithmetics.h"

using namespace std;

/*
constexpr int P = 1e9+7;

int Add(int a, int b) {
	int ret = a%P;
	ret = (ret<0 ? P+ret : ret) + (b%P);
	return (ret>=0 ? ret%P : ret+P);
}

int Sub(int a, int b) {
	int ret = a%P;
	ret = (ret<0 ? P+ret : ret) - (b%P);
	return (ret>=0 ? ret%P : ret+P);
}

int Mul(int a, int b) {
	int ret = (1ll*(a%P) * (b%P)) % P;
	return (ret<0 ? P+ret : ret);
}

int modpow(int base, int exp, int modulus=P) {
  base %= modulus;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = (1ll*result * base) % modulus;
    base = (1ll*base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
int modinv(int a, int modulus=P) {
  return modpow(a,modulus-2);
}

int Div(int a, int b) {
	int ret = b%P;
	ret = (1ll*(a%P) * modinv(ret<0 ? P+ret : ret)) % P;
	return (ret<0 ? P+ret : ret);
}
*/
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int r, c, q;
	cin >> r >> c >> q;
	int logr = log2(r)+1;
	vector<vector<vector<int>>> jump(logr, vector<vector<int>> (c+1, vector<int> (c+1, 0)));
	for (int i = 1; i <= c; i++) {
		jump[0][i][i]++;
		if (i > 1) jump[0][i][i-1]++;
		if (i < c) jump[0][i][i+1]++;
	}
	for (int l = 1; l < logr; l++) {
		//~ cout << l << ": " << endl;
		for (int j = 1; j <= c; j++) {
			for (int k = 1; k <= c; k++) {
				jump[l][1][j] = Add(jump[l][1][j], Mul(jump[l-1][1][k], jump[l-1][k][j]));
				jump[l][j][1] = jump[l][1][j];
				jump[l][c][c-j+1] = jump[l][1][j];
				jump[l][c-j+1][c] = jump[l][1][j];
			}
		}
		for (int i = 2; i <= c/2; i++) {
			for (int j = i; j <= c/2; j++) {
				jump[l][i][j] = Add(jump[l][i-1][j-1], jump[l][1][i+j-1]);
			}
		}
		for (int i = c-1; i > c/2; i--) {
			for (int j = 2; j <= c-i+1; j++) {
				jump[l][i][j] = Add(jump[l][i+1][j-1], jump[l][1][i-j+1]);
			}
		}
		for (int i = 2; i <= c/2; i++) {
			for (int j = i; j <= c/2; j++) {
				jump[l][j][i] = jump[l][i][j];
				jump[l][c-j+1][c-i+1] = jump[l][i][j];
				jump[l][c-i+1][c-j+1] = jump[l][i][j];
			}
		}
		for (int i = c-1; i > c/2; i--) {
			for (int j = 2; j <= c-i+1; j++) {
				jump[l][j][i] = jump[l][i][j];
				jump[l][c-j+1][c-i+1] = jump[l][i][j];
				jump[l][c-i+1][c-j+1] = jump[l][i][j];
			}
		}
	}
	vector<vector<int>> dp1(c+1, vector<int> (c+1, 0));
	for (int i = 1; i <= c; i++) dp1[i][i] = 1;
	vector<vector<int>> dp2(c+1, vector<int> (c+1, 0));
	int tmpy = r-1;
	//~ cout << "EEK" << endl;
	for (int l = logr-1; l >= 0; l--) {
		if (tmpy >= (1<<l)) {
			//~ cout << "JA " << l << " " << (1<<l) << endl;
			tmpy -= (1<<l);
			for (int j = 1; j <= c; j++) {
				for (int k = 1; k <= c; k++) {
					dp2[1][j] = Add(dp2[1][j], Mul(dp1[1][k], jump[l][k][j]));
					dp2[j][1] = dp2[1][j];
					dp2[c][c-j+1] = dp2[1][j];
					dp2[c-j+1][c] = dp2[1][j];
				}
			}	
			for (int i = 2; i <= c/2; i++) {
				for (int j = i; j <= c/2; j++) {
					dp2[i][j] = Add(dp2[i-1][j-1], dp2[1][i+j-1]);
				}
			}
			for (int i = c-1; i > c/2; i--) {
				for (int j = 2; j <= c-i+1; j++) {
					dp2[i][j] = Add(dp2[i+1][j-1], dp2[1][i-j+1]);
				}
			}
			for (int i = 2; i <= c/2; i++) {
				for (int j = i; j <= c/2; j++) {
					dp2[j][i] = dp2[i][j];
					dp2[c-j+1][c-i+1] = dp2[i][j];
					dp2[c-i+1][c-j+1] = dp2[i][j];
				}
			}
			for (int i = c-1; i > c/2; i--) {
				for (int j = 2; j <= c-i+1; j++) {
					dp2[j][i] = dp2[i][j];
					dp2[c-j+1][c-i+1] = dp2[i][j];
					dp2[c-i+1][c-j+1] = dp2[i][j];
				}
			}
			dp1 = dp2;
			dp2 = vector<vector<int>> (c+1, vector<int> (c+1, 0));
		}
	}
	for (int i = 0; i < q; i++) {
		char s;
		int a, b;
		cin >> s >> a >> b;
		if (s == 'K') {
			cout << r-1 << " " << dp1[a][b] << "\n";
		} else cout << "0 0" << endl;
	}
}

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