QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134086 | #4939. Red Black Ball | BoulevardDust | TL | 54ms | 4088kb | C++14 | 2.8kb | 2023-08-03 00:24:34 | 2023-08-03 00:24:35 |
Judging History
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...