QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#498485 | #8776. Not Another Constructive! | z | WA | 1ms | 5448kb | C++14 | 1.4kb | 2024-07-30 15:29:52 | 2024-07-30 15:29:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[50];
char t[50];
bitset<2501> f[41][41][41];
void dfs(int st,int a,int b,int c){
if(st==0){
for(int i=1;i<=n;i++) putchar(t[i]);
exit(0);
}
if(s[st]=='N'){
t[st]='N';
dfs(st-1,a-1,b,c);
}else if(s[st]=='A'){
t[st]='A';
dfs(st-1,a,b,c-a*b);
}else if(s[st]=='C'){
t[st]='C';
dfs(st-1,a,b+1,c);
}else if('A'<=s[st]&&s[st]<='Z'){
t[st]=s[st];
dfs(st-1,a,b,c);
}else{
if(a&&f[st-1][a-1][b][c]){
t[st]='N';
dfs(st-1,a-1,b,c);
}
if(a*b<=c&&f[st-1][a][b][c-a*b]){
t[st]='A';
dfs(st-1,a,b,c-a*b);
}
if(f[st-1][a][b+1][c]){
t[st]='C';
dfs(st-1,a,b+1,c);
}
if(f[st-1][a][b][c]){
t[st]='B';
dfs(st-1,a,b,c);
}
}
}
int main(){
scanf("%d%d%s",&n,&m,s+1);
for(int i=0;i<=n;i++) f[0][0][i][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
for(int k=0;k<=n-i;k++){
if(s[i]=='N'){
f[i][j+1][k]|=f[i-1][j][k];
}else if(s[i]=='A'){
f[i][j][k]|=(f[i-1][j][k]<<j*k);
}else if(s[i]=='C'){
if(k) f[i][j][k-1]|=f[i-1][j][k];
}else if('A'<=s[i]&&s[i]<='Z'){
f[i][j][k]|=f[i-1][j][k];
}else{
f[i][j+1][k]|=f[i-1][j][k];
f[i][j][k]|=(f[i-1][j][k]<<j*k);
if(k) f[i][j][k-1]|=f[i-1][j][k];
f[i][j][k]|=f[i-1][j][k];
}
}
}
}
for(int i=0;i<=n;i++){
if(f[n][i][0][m]){
dfs(n,i,0,m);
}
}
puts("-1");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5448kb
input:
22 2 N??A??????C???????????
output:
NCCABBBBBACAAAAAAAAAAA
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 4852kb
input:
18 0 COUNTINGSATELLITES
output:
COUNTINGSATELLITES
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 1 ??
output:
-1
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 0 ?
output:
A
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 0 N
output:
N
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 0 X
output:
X
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 1 ?
output:
-1
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 1 N
output:
-1
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 1 X
output:
-1
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 0 ??
output:
AA
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
2 0 N?
output:
NA
result:
ok correct
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
2 0 ?C
output:
-1
result:
wrong answer returned false