oj.uz

Submission #792895

# Submission time Handle Problem Language Result Execution time Memory
792895 2023-07-25T10:39:38 Z ymm Chess Rush (CEOI20_chessrush) C++17
28 / 100
 2000 ms 8544 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;
}

#define MOD(x) ((x) >= mod? (x)-mod: (x))

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void calc_king(int n)
{
	static karr b;
	if (n <= 128) {
		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] = MOD(b[i][0] + b[i][1]);
				Loop (j,1,m-1)
					king_table[i][j] = MOD(MOD(b[i][j-1] + b[i][j]) + b[i][j+1]);
				king_table[i][m-1] = MOD(b[i][m-2] + b[i][m-1]);
			}
		}
		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] = MOD(b[i][0] + b[i][1]);
			Loop (j,1,m-1)
				king_table[i][j] = MOD(MOD(b[i][j-1] + b[i][j]) + b[i][j+1]);
			king_table[i][m-1] = MOD(b[i][m-2] + b[i][m-1]);
		}
	} 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 4 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 3 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4436 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 14 ms 4568 KB Output is correct
2 Correct 14 ms 4820 KB Output is correct
3 Correct 13 ms 4812 KB Output is correct
4 Correct 12 ms 4472 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4568 KB Output is correct
2 Correct 14 ms 4820 KB Output is correct
3 Correct 13 ms 4812 KB Output is correct
4 Correct 12 ms 4472 KB Output is correct
5 Correct 14 ms 4576 KB Output is correct
6 Correct 6 ms 4580 KB Output is correct
7 Correct 14 ms 4820 KB Output is correct
8 Correct 14 ms 4852 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4568 KB Output is correct
2 Correct 14 ms 4820 KB Output is correct
3 Correct 13 ms 4812 KB Output is correct
4 Correct 12 ms 4472 KB Output is correct
5 Correct 14 ms 4576 KB Output is correct
6 Correct 6 ms 4580 KB Output is correct
7 Correct 14 ms 4820 KB Output is correct
8 Correct 14 ms 4852 KB Output is correct
9 Correct 22 ms 8544 KB Output is correct
10 Correct 27 ms 8524 KB Output is correct
11 Correct 72 ms 8436 KB Output is correct
12 Correct 76 ms 8532 KB Output is correct
13 Correct 24 ms 8524 KB Output is correct
14 Correct 28 ms 8516 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4568 KB Output is correct
2 Correct 14 ms 4820 KB Output is correct
3 Correct 13 ms 4812 KB Output is correct
4 Correct 12 ms 4472 KB Output is correct
5 Correct 14 ms 4576 KB Output is correct
6 Correct 6 ms 4580 KB Output is correct
7 Correct 14 ms 4820 KB Output is correct
8 Correct 14 ms 4852 KB Output is correct
9 Correct 22 ms 8544 KB Output is correct
10 Correct 27 ms 8524 KB Output is correct
11 Correct 72 ms 8436 KB Output is correct
12 Correct 76 ms 8532 KB Output is correct
13 Correct 24 ms 8524 KB Output is correct
14 Correct 28 ms 8516 KB Output is correct
15 Correct 23 ms 8532 KB Output is correct
16 Correct 25 ms 8524 KB Output is correct
17 Execution timed out 2072 ms 8444 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

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