QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#639936 | #8776. Not Another Constructive! | Tenshi | RE | 44ms | 112140kb | C++23 | 2.3kb | 2024-10-14 00:10:39 | 2024-10-14 00:10:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
inline void read(int &x){
int s=0; x=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=13*13*14+5;
int n, K;
string s;
bitset<N> f[41][41][401];
void print(int idx, int a, int b, int c){
if(!idx) return;
int pi, pa, pb, pc;
char res, cur=s[idx];
if(cur=='N'){
pi=idx-1, pa=a-1, pb=b, pc=c;
}
else if(cur=='A'){
pi=idx-1, pa=a, pb=b-a, pc=c;
}
else if(cur=='C'){
pi=idx-1, pa=a, pb=b, pc=c-b;
}
else if(isalpha(cur)){
pi=idx-1, pa=a, pb=b, pc=c;
}
else{
if(f[idx-1][a-1][b][c]) pi=idx-1, pa=a-1, pb=b, pc=c, res='N';
else if(f[idx-1][a][b-a][c]) pi=idx-1, pa=a, pb=b-a, pc=c, res='A';
else if(f[idx-1][a][b][c-b]) pi=idx-1, pa=a, pb=b, pc=c-b, res='C';
else if(f[idx-1][a][b][c]) pi=idx-1, pa=a, pb=b, pc=c, res='T';
}
if(isalpha(cur)) res=cur;
print(pi, pa, pb, pc);
putchar(res);
}
signed main(){
cin>>n>>K;
cin>>s;
s=" "+s;
// debug(sizeof f);
f[0][0][0][0]=1;
rep(i, 1, n){
char c=s[i];
if(c=='N'){
rep(a, 1, 40) rep(b, 0, 400) f[i][a][b]=f[i-1][a-1][b];
}
else if(c=='A'){
rep(a, 0, 40) rep(b, a, 400) f[i][a][b]=f[i-1][a][b-a];
}
else if(c=='C'){
rep(a, 0, 40) rep(b, 0, 400) f[i][a][b]=f[i-1][a][b]<<b;
}
else if(isalpha(c)){
rep(a, 0, 40) rep(b, 0, 400) f[i][a][b]=f[i-1][a][b];
}
else{
rep(a, 0, 40) rep(b, 0, 400) f[i][a][b]=f[i-1][a][b];
rep(a, 1, 40) rep(b, 0, 400) f[i][a][b]|=f[i-1][a-1][b];
rep(a, 0, 40) rep(b, a, 400) f[i][a][b]|=f[i-1][a][b-a];
rep(a, 0, 40) rep(b, 0, 400) f[i][a][b]|=f[i-1][a][b]<<b;
// debug(f[1][1][0][0]);
// debug(f[2][1][1][0]);
}
}
int A=-1, B;
rep(a, 0, 40) rep(b, 0, 400) if(f[n][a][b][K]){
A=a, B=b;
}
if(A==-1){
puts("-1");
return 0;
}
print(n, A, B, K);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 44ms
memory: 112140kb
input:
22 2 N??A??????C???????????
output:
NCNANNNNNNCNNNNNNNNNNN
result:
ok correct
Test #2:
score: 0
Accepted
time: 23ms
memory: 93656kb
input:
18 0 COUNTINGSATELLITES
output:
COUNTINGSATELLITES
result:
ok correct
Test #3:
score: 0
Accepted
time: 3ms
memory: 15888kb
input:
2 1 ??
output:
-1
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 9620kb
input:
1 0 ?
output:
N
result:
ok correct
Test #5:
score: 0
Accepted
time: 2ms
memory: 11712kb
input:
1 0 N
output:
N
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 11932kb
input:
1 0 X
output:
X
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 11732kb
input:
1 1 ?
output:
-1
result:
ok correct
Test #8:
score: 0
Accepted
time: 1ms
memory: 9744kb
input:
1 1 N
output:
-1
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 9664kb
input:
1 1 X
output:
-1
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 13848kb
input:
2 0 ??
output:
NN
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 15804kb
input:
2 0 N?
output:
NN
result:
ok correct
Test #12:
score: 0
Accepted
time: 5ms
memory: 15892kb
input:
2 0 ?C
output:
NC
result:
ok correct
Test #13:
score: 0
Accepted
time: 4ms
memory: 15976kb
input:
2 1 N?
output:
-1
result:
ok correct
Test #14:
score: 0
Accepted
time: 2ms
memory: 16028kb
input:
2 1 ?C
output:
-1
result:
ok correct
Test #15:
score: 0
Accepted
time: 5ms
memory: 19968kb
input:
3 1 ???
output:
NAC
result:
ok correct
Test #16:
score: 0
Accepted
time: 7ms
memory: 19928kb
input:
3 1 N??
output:
NAC
result:
ok correct
Test #17:
score: 0
Accepted
time: 3ms
memory: 19980kb
input:
3 1 ?A?
output:
NAC
result:
ok correct
Test #18:
score: 0
Accepted
time: 7ms
memory: 19956kb
input:
3 1 ??C
output:
NAC
result:
ok correct
Test #19:
score: 0
Accepted
time: 5ms
memory: 19972kb
input:
3 1 NA?
output:
NAC
result:
ok correct
Test #20:
score: 0
Accepted
time: 2ms
memory: 19924kb
input:
3 1 N?C
output:
NAC
result:
ok correct
Test #21:
score: 0
Accepted
time: 2ms
memory: 19860kb
input:
3 1 ?AC
output:
NAC
result:
ok correct
Test #22:
score: 0
Accepted
time: 11ms
memory: 26112kb
input:
4 1 ????
output:
NACN
result:
ok correct
Test #23:
score: 0
Accepted
time: 7ms
memory: 26236kb
input:
4 1 X???
output:
XNAC
result:
ok correct
Test #24:
score: 0
Accepted
time: 3ms
memory: 26048kb
input:
4 1 ???Z
output:
NACZ
result:
ok correct
Test #25:
score: 0
Accepted
time: 8ms
memory: 26072kb
input:
4 1 ?AA?
output:
-1
result:
ok correct
Test #26:
score: 0
Accepted
time: 10ms
memory: 24064kb
input:
4 1 N???
output:
NACN
result:
ok correct
Test #27:
score: -100
Runtime Error
input:
4 1 ?N??