QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#545778#8776. Not Another Constructive!CCF_NOI#WA 192ms951544kbC++202.9kb2024-09-03 17:11:202024-09-03 17:11:21

Judging History

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

  • [2024-09-03 17:11:21]
  • 评测
  • 测评结果:WA
  • 用时:192ms
  • 内存:951544kb
  • [2024-09-03 17:11:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,k;
bitset<305>vis1[22][22][102],vis2[22][22][102];
string a,f1[22][22][102][305],f2[22][22][102][305];
void solve1(int m)
{
	f1[0][0][0][0]="";
	vis1[0][0][0][0]=1;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<=i;j++)
		{
			for(int k=0;k<=(i>>1)*(i+1>>1);k++)
			{
				for(int l=0;l<=300;l++)if(vis1[i][j][k][l])
				{
					if(a[i]=='?'||a[i]=='N')
					{
						if(!vis1[i+1][j+1][k][l])
						{
							vis1[i+1][j+1][k][l]=1;
							f1[i+1][j+1][k][l]=f1[i][j][k][l]+'N';
						}
					}
					if(a[i]=='?'||a[i]=='A')
					{
						if(!vis1[i+1][j][k+j][l])
						{
							vis1[i+1][j][k+j][l]=1;
							f1[i+1][j][k+j][l]=f1[i][j][k][l]+'A';
						}
					}
					if(a[i]=='?'||a[i]=='C')
					{
						if(!vis1[i+1][j][k][l+k])
						{
							vis1[i+1][j][k][l+k]=1;
							f1[i+1][j][k][l+k]=f1[i][j][k][l]+'C';
						}
					}
					if(a[i]!='N'&&a[i]!='A'&&a[i]!='C')
					{
						if(!vis1[i+1][j][k][l])
						{
							vis1[i+1][j][k][l]=1;
							f1[i+1][j][k][l]=f1[i][j][k][l]+(a[i]=='?'?'B':a[i]);
						}
					}
				}
			}
		}
	}
}
void solve2(int m)
{
	string a=::a;
	reverse(a.begin(),a.end());
	f2[0][0][0][0]="";
	vis2[0][0][0][0]=1;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<=i;j++)
		{
			for(int k=0;k<=(i>>1)*(i+1>>1);k++)
			{
				for(int l=0;l<=300;l++)if(vis2[i][j][k][l])
				{
					if(a[i]=='?'||a[i]=='C')
					{
						if(!vis2[i+1][j+1][k][l])
						{
							vis2[i+1][j+1][k][l]=1;
							f2[i+1][j+1][k][l]=f2[i][j][k][l]+'C';
						}
					}
					if(a[i]=='?'||a[i]=='A')
					{
						if(!vis2[i+1][j][k+j][l])
						{
							vis2[i+1][j][k+j][l]=1;
							f2[i+1][j][k+j][l]=f2[i][j][k][l]+'A';
						}
					}
					if(a[i]=='?'||a[i]=='N')
					{
						if(!vis2[i+1][j][k][l+k])
						{
							vis2[i+1][j][k][l+k]=1;
							f2[i+1][j][k][l+k]=f2[i][j][k][l]+'N';
						}
					}
					if(a[i]!='N'&&a[i]!='A'&&a[i]!='C')
					{
						if(!vis2[i+1][j][k][l])
						{
							vis2[i+1][j][k][l]=1;
							f2[i+1][j][k][l]=f2[i][j][k][l]+(a[i]=='?'?'B':a[i]);
						}
					}
				}
			}
		}
	}
}
int main()
{
	cin>>n>>k>>a;
	if(n<=20)
	{
		solve1(n);
		for(int i=0;i<=n;i++)for(int j=0;j<=n*n;j++)if(vis1[n][i][j][k])
		{
			cout<<f1[n][i][j][k]<<'\n';
			return 0;
		}
		cout<<"-1\n";
		return 0;
	}
	int m=n>>1;
	solve1(m);
	solve2(n-m);
	for(int i1=0;i1<=m;i1++)for(int j1=0;j1<=(m>>1)*(m+1>>1);j1++)
	{
		for(int i2=0;i2<=n-m;i2++)for(int j2=0;j2<=(n-m>>1)*(n-m+1>>1);j2++)
		{
			int sum=i1*j2+j1*i2;
			if(sum>k)continue;
			int l=k-sum;
			if(l>600)continue;
			for(int l1=max(l-300,0);l1<=min(l,300);l1++)if(vis1[m][i1][j1][l1])
			{
				int l2=l-l1;
				if(vis2[n-m][i2][j2][l2])
				{
					cout<<f1[m][i1][j1][l1];
					reverse(f2[n-m][i2][j2][l2].begin(),f2[n-m][i2][j2][l2].end());
					cout<<f2[n-m][i2][j2][l2]<<'\n';
					return 0;
				}
			}
		}
	}
	cout<<"-1\n";
}

详细

Test #1:

score: 100
Accepted
time: 143ms
memory: 945240kb

input:

22 2
N??A??????C???????????

output:

NCCABBBBBCCAAAAAAAAAAA

result:

ok correct

Test #2:

score: 0
Accepted
time: 137ms
memory: 944768kb

input:

18 0
COUNTINGSATELLITES

output:

COUNTINGSATELLITES

result:

ok correct

Test #3:

score: 0
Accepted
time: 95ms
memory: 944900kb

input:

2 1
??

output:

-1

result:

ok correct

Test #4:

score: 0
Accepted
time: 120ms
memory: 944596kb

input:

1 0
?

output:

A

result:

ok correct

Test #5:

score: 0
Accepted
time: 92ms
memory: 944868kb

input:

1 0
N

output:

N

result:

ok correct

Test #6:

score: 0
Accepted
time: 116ms
memory: 944712kb

input:

1 0
X

output:

X

result:

ok correct

Test #7:

score: 0
Accepted
time: 128ms
memory: 944880kb

input:

1 1
?

output:

-1

result:

ok correct

Test #8:

score: 0
Accepted
time: 143ms
memory: 944708kb

input:

1 1
N

output:

-1

result:

ok correct

Test #9:

score: 0
Accepted
time: 115ms
memory: 944576kb

input:

1 1
X

output:

-1

result:

ok correct

Test #10:

score: 0
Accepted
time: 116ms
memory: 944728kb

input:

2 0
??

output:

AA

result:

ok correct

Test #11:

score: 0
Accepted
time: 112ms
memory: 944720kb

input:

2 0
N?

output:

NC

result:

ok correct

Test #12:

score: 0
Accepted
time: 128ms
memory: 944892kb

input:

2 0
?C

output:

AC

result:

ok correct

Test #13:

score: 0
Accepted
time: 152ms
memory: 944724kb

input:

2 1
N?

output:

-1

result:

ok correct

Test #14:

score: 0
Accepted
time: 127ms
memory: 944692kb

input:

2 1
?C

output:

-1

result:

ok correct

Test #15:

score: 0
Accepted
time: 192ms
memory: 944908kb

input:

3 1
???

output:

NAC

result:

ok correct

Test #16:

score: 0
Accepted
time: 163ms
memory: 944728kb

input:

3 1
N??

output:

NAC

result:

ok correct

Test #17:

score: 0
Accepted
time: 137ms
memory: 944772kb

input:

3 1
?A?

output:

NAC

result:

ok correct

Test #18:

score: 0
Accepted
time: 119ms
memory: 944732kb

input:

3 1
??C

output:

NAC

result:

ok correct

Test #19:

score: 0
Accepted
time: 110ms
memory: 944720kb

input:

3 1
NA?

output:

NAC

result:

ok correct

Test #20:

score: 0
Accepted
time: 129ms
memory: 944888kb

input:

3 1
N?C

output:

NAC

result:

ok correct

Test #21:

score: 0
Accepted
time: 150ms
memory: 944664kb

input:

3 1
?AC

output:

NAC

result:

ok correct

Test #22:

score: 0
Accepted
time: 115ms
memory: 944644kb

input:

4 1
????

output:

ANAC

result:

ok correct

Test #23:

score: 0
Accepted
time: 135ms
memory: 944716kb

input:

4 1
X???

output:

XNAC

result:

ok correct

Test #24:

score: 0
Accepted
time: 116ms
memory: 944696kb

input:

4 1
???Z

output:

NACZ

result:

ok correct

Test #25:

score: 0
Accepted
time: 128ms
memory: 944916kb

input:

4 1
?AA?

output:

-1

result:

ok correct

Test #26:

score: 0
Accepted
time: 123ms
memory: 944752kb

input:

4 1
N???

output:

NCAC

result:

ok correct

Test #27:

score: 0
Accepted
time: 122ms
memory: 944748kb

input:

4 1
?N??

output:

ANAC

result:

ok correct

Test #28:

score: 0
Accepted
time: 115ms
memory: 944684kb

input:

4 1
??N?

output:

NANC

result:

ok correct

Test #29:

score: 0
Accepted
time: 96ms
memory: 944692kb

input:

4 1
???N

output:

NACN

result:

ok correct

Test #30:

score: 0
Accepted
time: 134ms
memory: 944680kb

input:

4 1
A???

output:

ANAC

result:

ok correct

Test #31:

score: 0
Accepted
time: 143ms
memory: 944880kb

input:

4 1
?A??

output:

NABC

result:

ok correct

Test #32:

score: 0
Accepted
time: 140ms
memory: 944920kb

input:

4 1
??A?

output:

ANAC

result:

ok correct

Test #33:

score: 0
Accepted
time: 115ms
memory: 944644kb

input:

4 1
???A

output:

NACA

result:

ok correct

Test #34:

score: 0
Accepted
time: 115ms
memory: 944680kb

input:

4 1
C???

output:

CNAC

result:

ok correct

Test #35:

score: 0
Accepted
time: 120ms
memory: 944744kb

input:

4 1
?C??

output:

NCAC

result:

ok correct

Test #36:

score: 0
Accepted
time: 104ms
memory: 944748kb

input:

4 1
??C?

output:

NACB

result:

ok correct

Test #37:

score: 0
Accepted
time: 119ms
memory: 944748kb

input:

4 1
???C

output:

ANAC

result:

ok correct

Test #38:

score: 0
Accepted
time: 107ms
memory: 944648kb

input:

5 4
?????

output:

NAACC

result:

ok correct

Test #39:

score: 0
Accepted
time: 120ms
memory: 944808kb

input:

6 14
??????

output:

-1

result:

ok correct

Test #40:

score: 0
Accepted
time: 120ms
memory: 944724kb

input:

7 14
???????

output:

-1

result:

ok correct

Test #41:

score: 0
Accepted
time: 104ms
memory: 945012kb

input:

8 43
????????

output:

-1

result:

ok correct

Test #42:

score: 0
Accepted
time: 127ms
memory: 944896kb

input:

9 55
?????????

output:

-1

result:

ok correct

Test #43:

score: 0
Accepted
time: 116ms
memory: 945100kb

input:

10 112
??????????

output:

-1

result:

ok correct

Test #44:

score: 0
Accepted
time: 124ms
memory: 945148kb

input:

11 110
???????????

output:

-1

result:

ok correct

Test #45:

score: 0
Accepted
time: 123ms
memory: 945068kb

input:

12 4
????????????

output:

AAAAAANACCCC

result:

ok correct

Test #46:

score: 0
Accepted
time: 153ms
memory: 945060kb

input:

13 193
?????????????

output:

-1

result:

ok correct

Test #47:

score: 0
Accepted
time: 131ms
memory: 945320kb

input:

14 91
??????????????

output:

NNNANAAACACCCC

result:

ok correct

Test #48:

score: 0
Accepted
time: 131ms
memory: 945128kb

input:

15 15
???????????????

output:

NACCCCCCCCCACCC

result:

ok correct

Test #49:

score: 0
Accepted
time: 127ms
memory: 946652kb

input:

16 261
????????????????

output:

-1

result:

ok correct

Test #50:

score: 0
Accepted
time: 116ms
memory: 948896kb

input:

17 514
?????????????????

output:

-1

result:

ok correct

Test #51:

score: -100
Wrong Answer
time: 124ms
memory: 951544kb

input:

18 678
??????????????????

output:



result:

wrong output format Unexpected end of file - token expected