QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639936#8776. Not Another Constructive!TenshiRE 44ms112140kbC++232.3kb2024-10-14 00:10:392024-10-14 00:10:40

Judging History

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

  • [2024-10-14 00:10:40]
  • 评测
  • 测评结果:RE
  • 用时:44ms
  • 内存:112140kb
  • [2024-10-14 00:10:39]
  • 提交

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??

output:


result: