QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#507699 | #8776. Not Another Constructive! | _log_ | WA | 2ms | 130524kb | C++14 | 3.1kb | 2024-08-06 20:18:54 | 2024-08-06 20:18:55 |
Judging History
answer
# include <bits/stdc++.h>
# define maxn 100100
# define rep(i, j, k) for(int i = j; i <= k; ++i)
# define per(i, j, k) for(int i = j; i >= k; --i)
using namespace std;
int n, m, ans;
int pre[45], nxt[45], que[45], nop[maxn];
int dp[41][41][41][2501];
string s;
inline int cub(int x) {int tmp = (x + 2) / 3; return tmp * tmp * tmp;}
void dfs(int i, int j, int k, int l) {
if(i == 0) return;
if(s[i] == 'N') dfs(i - 1, j - 1, k, l), cout << 'N';
else if(s[i] == 'A') dfs(i - 1, j, k, l - j * k), cout << 'A';
else if(s[i] == 'C') dfs(i - 1, j, k + 1, l), cout << 'C';
else if(s[i] == '?')
if(dp[i - 1][j][k][l]) dfs(i - 1, j, k, l), cout << 'B';
else if(dp[i - 1][j - 1][k][l]) dfs(i - 1, j - 1, k, l), cout << 'N';
else if(l >= j * k && dp[i - 1][j][k][l - j * k]) dfs(i - 1, j, k, l - j * k), cout << 'A';
else dfs(i - 1, j, k + 1, l), cout << 'C';
else dfs(i - 1, j, k, l), cout << s[i];
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> s; s = ' ' + s;
rep(i, 1, n) {
pre[i] = pre[i - 1] + (s[i] == 'N');
if(s[i] != 'N' && s[i] != 'A' && s[i] != 'C' && s[i] != '?') nop[i] = nop[i - 1] + 1;
que[i] = que[i - 1] + (s[i] == '?');
}
per(i, n, 1) nxt[i] = nxt[i + 1] + (s[i] == 'C');
// rep(i, 1, n) cout << pre[i] << ' '; cout << '\n';
// rep(i, 1, n) cout << que[i] << ' '; cout << '\n';
// rep(i, 1, n) cout << nxt[i] << ' '; cout << '\n';
// cerr << "I love Furina forever\n";
rep(i, 0, n) dp[0][0][i][0] = 1;
rep(i, 1, n) {
rep(j, pre[i], pre[i] + que[i]) {
rep(k, nxt[i + 1], nxt[i + 1] + que[n] - que[i]) {
rep(l, 0, m) {
if(s[i] == 'N') dp[i][j][k][l] = dp[i - 1][j - 1][k][l];
else if(s[i] == 'C') dp[i][j][k][l] = dp[i - 1][j][k + 1][l];
else if(s[i] == 'A' && l >= j * k) dp[i][j][k][l] = dp[i - 1][j][k][l - j * k];
else if(s[i] == '?') {
if(j > 0) dp[i][j][k][l] = dp[i - 1][j - 1][k][l];
if(l >= j * k) dp[i][j][k][l] = dp[i][j][k][l] || dp[i - 1][j][k][l - j * k];
dp[i][j][k][l] = dp[i][j][k][l] || dp[i - 1][j][k + 1][l];
dp[i][j][k][l] = dp[i][j][k][l] || dp[i - 1][j][k][l];
// dp[i][j][k][l] = dp[i - 1][j - 1][k][l] || dp[i - 1][j][k + 1][l] || dp[i - 1][j][k][l - j * k] || dp[i - 1][j][k][l];
}
else dp[i][j][k][l] = dp[i - 1][j][k][l];
// cerr << i << ' ' << j << ' ' << k << ' ' << l << ' ' << dp[i][j][k][l] << '\n';
}
}
}
}
// cerr << "Genshin Impact\n";
rep(i, 0, n) ans = ans || dp[n][i][0][m];
// cerr << dp[2][0][0][m] << ' ' << dp[2][1][0][m] << ' ' << dp[2][2][0][m] << '\n';
if(ans == 0) {cout << -1; return 0;}
// return 0;
rep(i, 0, n) if(dp[n][i][0][m]) {dfs(n, i, 0, m), cout << '\n'; break;}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 130524kb
input:
22 2 N??A??????C???????????
output:
NABABBBBBBCBBBBBBBBBBB
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 40468kb
input:
18 0 COUNTINGSATELLITES
output:
COUNTINGSATELLITES
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 7724kb
input:
2 1 ??
output:
-1
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 0 ?
output:
B
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
1 0 N
output:
N
result:
ok correct
Test #6:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
1 0 X
output:
X
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 1 ?
output:
-1
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 5592kb
input:
1 1 N
output:
-1
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 5608kb
input:
1 1 X
output:
-1
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 0 ??
output:
BB
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 7632kb
input:
2 0 N?
output:
NB
result:
ok correct
Test #12:
score: 0
Accepted
time: 1ms
memory: 9904kb
input:
2 0 ?C
output:
BC
result:
ok correct
Test #13:
score: 0
Accepted
time: 1ms
memory: 9904kb
input:
2 1 N?
output:
-1
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 5680kb
input:
2 1 ?C
output:
-1
result:
ok correct
Test #15:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
3 1 ???
output:
NAC
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 9732kb
input:
3 1 N??
output:
NAC
result:
ok correct
Test #17:
score: 0
Accepted
time: 2ms
memory: 12028kb
input:
3 1 ?A?
output:
NAC
result:
ok correct
Test #18:
score: 0
Accepted
time: 1ms
memory: 11808kb
input:
3 1 ??C
output:
NAC
result:
ok correct
Test #19:
score: 0
Accepted
time: 1ms
memory: 9752kb
input:
3 1 NA?
output:
NAC
result:
ok correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 13868kb
input:
3 1 N?C
output:
NAC
result:
ok correct
Test #21:
score: 0
Accepted
time: 1ms
memory: 11820kb
input:
3 1 ?AC
output:
NAC
result:
ok correct
Test #22:
score: 0
Accepted
time: 1ms
memory: 11844kb
input:
4 1 ????
output:
NACB
result:
ok correct
Test #23:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
4 1 X???
output:
XNAC
result:
ok correct
Test #24:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
4 1 ???Z
output:
NACZ
result:
ok correct
Test #25:
score: -100
Wrong Answer
time: 1ms
memory: 7968kb
input:
4 1 ?AA?
output:
CAAC
result:
wrong answer string is wrong length