oj.uz

Submission #792884

# Submission time Handle Problem Language Result Execution time Memory
792884 2023-07-25T10:29:43 Z ymm Chess Rush (CEOI20_chessrush) C++17
28 / 100
 2000 ms 8652 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int mod = 1e9+7;
const int N = 1024;
ll fct[N], fcti[N];
int n, m;

ll pw(ll x,ll y){ll a=1;while(y){if(y&1)a=a*x%mod;x=x*x%mod;y/=2;}return a;}
ll C(int n, int r) {
	ll ans = 1;
	Loop (i,n-r+1,n+1)
		ans = ans*i % mod;
	ans = ans * fcti[r]%mod;
	return ans;
}
void init() {
	fct[0] = fcti[0] = 1;
	Loop (i,1,N) {
		fct[i] = fct[i-1]*i % mod;
		fcti[i] = pw(fct[i], mod-2);
	}
}

typedef unsigned karr[N][N];
karr king_table;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
unsigned mul(unsigned *a, unsigned *b)
{
	ll ans = 0;
	Loop (i,0,N)
		ans = (ans + (ll)a[i] * b[i]) % mod;
	return ans;
	//typedef unsigned long long ull;
	//ull ans[4] = {};
	//for (int i = 0; i < N; i += 64) {
	//	for (int j = 0; j < 64; j += 4) {
	//		for (int k = 0; k < 4; ++k)
	//			ans[k] += (ull)a[i+j+k] * b[i+j+k];
	//	}
	//	Loop (k,0,4)
	//		ans[k] %= mod;
	//}
	//return (ans[0] + ans[1] + ans[2] + ans[3]) % mod;
}

void calc_king(int n)
{
	static karr b;
	if (n <= 32) {
		Loop (i,0,m) Loop (j,0,m)
			king_table[i][j] = i == j;
		while (n--) {
			memcpy(b, king_table, sizeof(king_table));
			Loop (i,0,m) {
				king_table[i][0] = (b[i][0] + b[i][1]) % mod;
				Loop (j,1,m-1)
					king_table[i][j] = (b[i][j-1] + b[i][j] + b[i][j+1]) % mod;
				king_table[i][m-1] = (b[i][m-2] + b[i][m-1]) % mod;
			}
		}
		return;
	}
	calc_king(n/2);
	Loop (i,0,m) Loop (j,0,m) {
		if (i > j || i+j >= m)
			continue;
		b[i][j] = mul(king_table[i], king_table[j]);
	}
	Loop (i,0,m) Loop (j,0,m) {
		if (i <= j || i+j >= m)
			continue;
		b[i][j] = b[j][i];
	}
	Loop (i,0,m) Loop (j,0,m) {
		if (i+j < m)
			continue;
		b[i][j] = b[m-1-i][m-1-j];
	}
	if (n%2 == 1) {
		Loop (i,0,m) {
			king_table[i][0] = (b[i][0] + b[i][1]) % mod;
			Loop (j,1,m-1)
				king_table[i][j] = (b[i][j-1] + b[i][j] + b[i][j+1]) % mod;
			king_table[i][m-1] = (b[i][m-2] + b[i][m-1]) % mod;
		}
	} else {
		memcpy(king_table, b, sizeof(king_table));
	}
}

pii pawn(int i, int j)
{
	return i == j? pii{n-1, 1}: pii{0, 0};
}
pii rook(int i, int j)
{
	return i == j? pii{1, 1}: pii{2, 2};
}
pii king(int i, int j)
{
	return {n-1, king_table[i][j]};
}
pii queen(int i, int j)
{
	// TODO
	return {0, 0};
}
pii bishop(int i, int j)
{
	// TODO
	return {0, 0};
}

map<char, pii (*)(int, int)> fn = {
	{'P', pawn},
	{'R', rook},
	{'K', king},
	{'Q', queen},
	{'B', bishop},
};

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> n >> m >> q;
	init();
	calc_king(n-1);
	while (q--) {
		char c;
		int i, j;
		cin >> c >> i >> j;
		--i; --j;
		auto [x, y] = fn[c](i, j);
		cout << x << ' ' << y << '\n';
	}
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4572 KB Output is correct
2 Correct 21 ms 4848 KB Output is correct
3 Correct 20 ms 8468 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4572 KB Output is correct
2 Correct 21 ms 4848 KB Output is correct
3 Correct 20 ms 8468 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 7 ms 4556 KB Output is correct
6 Correct 6 ms 4556 KB Output is correct
7 Correct 20 ms 8524 KB Output is correct
8 Correct 22 ms 4852 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4572 KB Output is correct
2 Correct 21 ms 4848 KB Output is correct
3 Correct 20 ms 8468 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 7 ms 4556 KB Output is correct
6 Correct 6 ms 4556 KB Output is correct
7 Correct 20 ms 8524 KB Output is correct
8 Correct 22 ms 4852 KB Output is correct
9 Correct 21 ms 8548 KB Output is correct
10 Correct 27 ms 8460 KB Output is correct
11 Correct 202 ms 8592 KB Output is correct
12 Correct 208 ms 8432 KB Output is correct
13 Correct 27 ms 8524 KB Output is correct
14 Correct 9 ms 8532 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4572 KB Output is correct
2 Correct 21 ms 4848 KB Output is correct
3 Correct 20 ms 8468 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 7 ms 4556 KB Output is correct
6 Correct 6 ms 4556 KB Output is correct
7 Correct 20 ms 8524 KB Output is correct
8 Correct 22 ms 4852 KB Output is correct
9 Correct 21 ms 8548 KB Output is correct
10 Correct 27 ms 8460 KB Output is correct
11 Correct 202 ms 8592 KB Output is correct
12 Correct 208 ms 8432 KB Output is correct
13 Correct 27 ms 8524 KB Output is correct
14 Correct 9 ms 8532 KB Output is correct
15 Correct 28 ms 8544 KB Output is correct
16 Correct 32 ms 8652 KB Output is correct
17 Execution timed out 2084 ms 8400 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -