QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134086#4939. Red Black BallBoulevardDustTL 54ms4088kbC++142.8kb2023-08-03 00:24:342023-08-03 00:24:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 00:24:35]
  • 评测
  • 测评结果:TL
  • 用时:54ms
  • 内存:4088kb
  • [2023-08-03 00:24:34]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#define mn 105
#define p 998244353

using namespace std;

int n, m, N, cnt[5], fac[mn], inv[mn];

int f[mn][mn], gg[mn][mn][55][2][2], num[mn];

vector<pair<int, int> > v;

int Pow(int a, int b) {
	int ans = 1;
	for(; b; b & 1 ? ans = 1ll * ans * a % p : 0, a = 1ll * a * a % p, b >>= 1);
	return ans;
}
int C(int n, int m) {
	if(n < 0 || m < 0 || n < m) return 0;
	return 1ll * fac[n] * inv[m] % p * inv[n - m] % p;
}

void Inc(int &a, int b) {
	if((a += b) >= p) a -= p;
}

int g(int l, int r, int k, int tl, int tr, int pl, int pr) {
	if(gg[l][r][k][tl][tr]) return gg[l][r][k][tl][tr];
	if(l > r) return gg[l][r][k][tl][tr] = k == 0;
	int t = tl, res = 0;
	for(int i = l; i <= r; ++i) {
		if(abs(v[i].first - pr) < abs(v[i].first - pl)) {
			t = tr;
		}
		int K = k - (t == 0);
		// printf("%d %d %d %d %d %d %d\n", l, r, v[i].first, K, t, max(0, K - (r - i)), min(i - l, K));
		for(int kk = max(0, K - (r - i)); kk <= min(i - l, K); ++kk) {
			Inc(res, 1ll * g(l, i - 1, kk, tl, t, pl, v[i].first) * g(i + 1, r, K - kk, t, tr, v[i].first, pr) % p * C(r - l, i - l) % p);
		}
	}
	// printf("%d %d %d %d %d %d %d %d\n", l, r, k, tl, tr, pl, pr, res);
	return gg[l][r][k][tl][tr] = res;
}

int main() {
	cin >> n >> m;
	N = n + m;
	fac[0] = 1;
	for(int i = 1; i <= N; ++i) {
		fac[i] = 1ll * fac[i - 1] * i % p;
	}
	inv[N] = Pow(fac[N], p - 2);
	for(int i = N - 1; i >= 0; --i) {
		inv[i] = 1ll * inv[i + 1] * (i + 1) % p;
	}
	int mx = 0;
	for(int i = 1; i <= n; ++i) {
		int x;
		string s;
		cin >> x >> s;
		mx = max(mx, x);
		int t = s == "BLACK";
		++cnt[t];
		v.push_back(make_pair(x, t));
	}
	sort(v.begin(), v.end());
	int tt = v[(int)v.size() - 1].second;
	v.push_back(make_pair(-1, v[0].second));
	for(int i = 1; i <= m; ++i) {
		int x;
		cin >> x;
		mx = max(mx, x);
		v.push_back(make_pair(x, 2));
	}
	v.push_back(make_pair(mx + 1, tt));
	sort(v.begin(), v.end());

	num[0] = 0;
	for(int i = 1; i < (int)v.size(); ++i) {
		num[i] = num[i - 1];
		if(v[i].second == 2) ++num[i];
	}
	f[0][0] = 1;
	int pre = 0;
	for(int i = 1; i < (int)v.size(); ++i) {
		if(v[i].second < 2) {
			for(int j = 0; j <= m; ++j) {
				// printf("%d %d %d %d\n", i, pre, num[i], num[pre]);
				for(int k = 0; k <= min(j, num[i] - num[pre]); ++k) {
					Inc(f[i][j], 1ll * f[pre][j - k] * g(pre + 1, i - 1, k, v[pre].second, v[i].second, v[pre].first, v[i].first) % p * C(num[i], num[pre]) % p);
				}
				// printf("%d %d %d\n", i, j, f[i][j]);
			}
			pre = i;
		}
	}
	int ans = 0;
	for(int j = 0; j <= m; ++j) {
		if(cnt[0] + j > cnt[1] + m - j) {
			// printf("%d\n", j);
			Inc(ans, f[(int)v.size() - 1][j]);
		}
	}
	printf("%d", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3668kb

input:

2 3
1 BLACK
10 RED
2 5 7

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

2 3
1 RED
10 BLACK
2 4 7

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

2 3
1 RED
10 BLACK
7 4 2

output:

6

result:

ok single line: '6'

Test #4:

score: 0
Accepted
time: 54ms
memory: 4076kb

input:

20 46
238846592 BLACK
199923217 RED
526626128 BLACK
62308338 RED
523811748 RED
59432 BLACK
273113193 BLACK
730729301 BLACK
973259012 RED
225318015 BLACK
611574923 RED
234880345 RED
485448383 BLACK
405607946 BLACK
747693124 RED
794086621 BLACK
91585417 BLACK
466451303 RED
244184598 RED
334788273 RED
...

output:

850819974

result:

ok single line: '850819974'

Test #5:

score: 0
Accepted
time: 2ms
memory: 4088kb

input:

24 46
1579 BLACK
10321 BLACK
7159 RED
13111 RED
11437 RED
277 BLACK
11623 BLACK
9391 RED
1765 RED
6787 BLACK
12367 BLACK
8647 RED
1207 RED
3811 RED
4183 BLACK
649 BLACK
11995 RED
6043 RED
2137 BLACK
8833 BLACK
7345 BLACK
463 RED
4369 RED
5113 BLACK
10507 7717 2509 4741 3997 5299 10879 8275 9763 5671...

output:

988708148

result:

ok single line: '988708148'

Test #6:

score: -100
Time Limit Exceeded

input:

2 49
747 RED
38197 BLACK
23966 11982 30707 20970 32205 23217 1496 24715 36699 20221 8986 8237 32954 29209 35950 18723 11233 13480 5990 22468 12731 27711 7488 2245 26213 16476 17225 34452 19472 15727 14978 9735 3743 4492 2994 33703 6739 17974 5241 21719 14229 28460 25464 29958 26962 35201 37448 10484...

output:


result: