QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#518987 | #8776. Not Another Constructive! | solar_express# | WA | 11ms | 59548kb | C++14 | 1.3kb | 2024-08-14 15:05:14 | 2024-08-14 15:05:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct NODE{
int ck,fa;
char ch;
}node[42][3000000];
int top[42];
int pd[50000000];
int n,k;
string s;
void add(int id,int N,int NA,int NAC,int fa,char ch){
int ck=N+NA*41+NAC*401*41;
if(id&&pd[ck]==id)return ;
if(NAC+NA*(n-id)+N*(n-id)*(n-id)/4+(n-id)*(n-id)*(n-id)/27<k)return ;
pd[ck]=id;
top[id]++;
node[id][top[id]].ck=ck;
node[id][top[id]].fa=fa;
node[id][top[id]].ch=ch;
if(top[id]>3000000){
cout<<"ERROR!! "<<endl;
}
}
void out(int zz,int x){
if(zz){
out(zz-1,node[zz][x].fa);
}putchar(node[zz][x].ch);
}
int main(){
cin>>n>>k>>s;
add(0,0,0,0,0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=top[i-1];j++){
int N,NA,NAC=node[i-1][j].ck/(401*41);
NA=node[i-1][j].ck/41-NAC*401;
N=node[i-1][j].ck-NAC*401*41-NA*41;
if(s[i-1]=='?'||(s[i-1]!='N'&&s[i-1]!='A'&&s[i-1]!='C'))add(i,N,NA,NAC,j,(s[i-1]=='?')? 'Q':s[i-1]);
if(s[i-1]=='?'||(s[i-1]=='N'))add(i,N+1,NA,NAC,j,'N');
if(s[i-1]=='?'||(s[i-1]=='A'))add(i,N,NA+N,NAC,j,'A');
if(s[i-1]=='?'||(s[i-1]=='C'))add(i,N,NA,NAC+NA,j,'C');
}
}
int ans=0;
for(int i=1;i<=top[n];i++){
int NAC=node[n][i].ck/(401*41);
if(NAC==k){
out(n,i);
ans=1;
break;
}
}
if(!ans)puts("-1");
}
详细
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 59548kb
input:
22 2 N??A??????C???????????
output:
result:
wrong answer illegal char