QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507699#8776. Not Another Constructive!_log_WA 2ms130524kbC++143.1kb2024-08-06 20:18:542024-08-06 20:18:55

Judging History

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

  • [2024-08-06 20:18:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:130524kb
  • [2024-08-06 20:18:54]
  • 提交

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