QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#742554 | #8776. Not Another Constructive! | actor | WA | 2ms | 14236kb | C++14 | 2.5kb | 2024-11-13 16:48:00 | 2024-11-13 16:48:03 |
Judging History
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