QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518987#8776. Not Another Constructive!solar_express#WA 11ms59548kbC++141.3kb2024-08-14 15:05:142024-08-14 15:05:14

Judging History

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

  • [2024-08-14 15:05:14]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:59548kb
  • [2024-08-14 15:05:14]
  • 提交

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