QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742554#8776. Not Another Constructive!actorWA 2ms14236kbC++142.5kb2024-11-13 16:48:002024-11-13 16:48:03

Judging History

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

  • [2024-11-13 16:48:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14236kb
  • [2024-11-13 16:48:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for (int i = (l); i <= (r); i++)
#define per(i,r,l) for (int i = (r); i >= (l); i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define maxn(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod = 998244353;
mt19937 gen(random_device{}());
ll rp(ll a,ll b) {ll res=1%mod;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int N = 43;
const int K = 2543;
int n, m;
char s[N], ans[N];
bitset<K> dp[N][N][N];

void dfs(int i, int j, int k, int l) {
    // cout << i << ' ' << j << ' ' << k << ' ' << l << endl;
    if (i==0) return ;
    ans[i] = s[i];
    if (s[i] == 'N') {
        dfs(i - 1, j - 1, k, l);
    } else if (s[i] == 'A') {
        dfs(i - 1, j, k, l - j * k);
    } else if (s[i] == 'C') {
        dfs(i - 1, j, k + 1, l);
    } else if (s[i] == '?') {
        if (j && dp[i-1][j-1][k][l]) dfs(i-1,j-1,k,l),ans[i]='N';
        else if(l>=j*k&&dp[i-1][j][k][l-j*k]) dfs(i-1,j,k,l-j*k),ans[i]='A';
        else if (dp[i-1][j][k+1][l]) dfs(i-1,j,k+1,l), ans[i]='C';
        else dfs(i-1,j,k,l), ans[i]='S';
    } else {
        dfs(i - 1, j, k, l);
        ans[i]='S';
    }
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    rep(j,0,n) dp[0][0][j].set(0);
    rep(i,1,n) {
        rep(j,0,i) rep(k,0,n - i) {
            if (s[i] == 'N') {
                if (j) dp[i][j][k] = dp[i][j][k] | dp[i - 1][j - 1][k];
            } else if (s[i] == 'A') {
                dp[i][j][k] = dp[i - 1][j][k]<<(j * k);
            } else if (s[i] == 'C') {
                dp[i][j][k] = dp[i][j][k] | dp[i - 1][j][k + 1];
            } else if (s[i] == '?') {
                if (j) dp[i][j][k] | dp[i - 1][j - 1][k];
                dp[i][j][k] = dp[i][j][k] | 
                dp[i - 1][j][k]<<(j * k) |
                dp[i - 1][j][k + 1] |
                dp[i - 1][j][k];
            } else {
                dp[i][j][k] = dp[i - 1][j][k];
            }
        }
    }
    rep(j,0,n) if (dp[n][j][0][m]) {
        // cout << j << endl;
        dfs(n, j, 0, m);
        printf("%s\n", ans + 1);
        return 0;
    }
    puts("-1");
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7416kb

input:

22 2
N??A??????C???????????

output:

NCCASSSSSACAAAAAAAAAAA

result:

ok correct

Test #2:

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

input:

18 0
COUNTINGSATELLITES

output:

CSSNSSNSSASSSSSSSS

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

2 1
??

output:

-1

result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

1 0
?

output:

A

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

1 0
N

output:

N

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

1 0
X

output:

S

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

1 1
?

output:

-1

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

1 1
N

output:

-1

result:

ok correct

Test #9:

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

input:

1 1
X

output:

-1

result:

ok correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

2 0
??

output:

AA

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

2 0
N?

output:

NA

result:

ok correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

2 0
?C

output:

AC

result:

ok correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

2 1
N?

output:

-1

result:

ok correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

2 1
?C

output:

-1

result:

ok correct

Test #15:

score: -100
Wrong Answer
time: 0ms
memory: 3704kb

input:

3 1
???

output:

-1

result:

wrong answer returned false