QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235493#7697. Impartial StringsPhantomThreshold#AC ✓47ms12444kbC++203.0kb2023-11-02 20:21:082023-11-02 20:21:09

Judging History

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

  • [2023-11-02 20:21:09]
  • 评测
  • 测评结果:AC
  • 用时:47ms
  • 内存:12444kb
  • [2023-11-02 20:21:08]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;

const int maxn = 505;

int checksubstring(string A,string B)
{
	int al=A.size(),bl=B.size();
	for(int i=0;i+bl<=al;i++)
	{
		if(A.substr(i,bl)==B) return 1;
	}
	return 0;
}
string A,S,T;
int av[30],sv[30],tv[30];
int checksize()
{
	int al=A.size(),sl=S.size(),tl=T.size();
	memset(av,0,sizeof av);
	for(int i=0;i<al;i++) av[A[i]-'a']=1;
	
	memset(sv,0,sizeof sv);
	int sn=0;
	for(int i=0;i<sl;i++)
	{
		int c=S[i]-'a';
		if(!av[c]) return 0;
		if(!sv[c]) sv[c]=1,sn++;
	}
	if(sn!=al) return 0;
	
	memset(tv,0,sizeof tv);
	int tn=0;
	for(int i=0;i<tl;i++)
	{
		int c=T[i]-'a';
		if(!av[c]) return 0;
		if(!tv[c]) tv[c]=1,tn++;
	}
	if(tn!=al) return 0;
	
	if(al!=2) return 0;
	
	return 1;
}

int fS[maxn],fT[maxn];
int goS[maxn][2],goT[maxn][2];
int a[maxn],b[maxn],an,bn;
int f[3][maxn][3][maxn];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>A>>S>>T;
		if( checksubstring(S,T) || checksubstring(T,S) )
		{
			cout<<"1\n";
			continue;
		}
		if(!checksize())
		{
			cout<<"0\n";
			continue;
		}
		char c0=A[0];
		
		an=0;
		for(auto c:S) a[++an]= (c==c0);
		bn=0;
		for(auto c:T) b[++bn]= (c==c0);
		
		goS[0][0]=goS[0][1]=0;
		goS[0][a[1]]=1;
		for(int i=1,k=0;i<=an;i++)
		{
			while(k&&a[k+1]!=a[i]) k=fS[k];
			if(i>1 && a[k+1]==a[i]) k++;
			fS[i]=k;
			
			for(int c=0;c<2;c++)
			{
				if(i<an && a[i+1]==c) goS[i][c]=i+1;
				else goS[i][c]=goS[k][c];
			}
		}
		
		goT[0][0]=goT[0][1]=0;
		goT[0][b[1]]=1;
		for(int i=1,k=0;i<=bn;i++)
		{
			while(k&&b[k+1]!=b[i]) k=fT[k];
			if(i>1 && b[k+1]==b[i]) k++;
			fT[i]=k;
			
			for(int c=0;c<2;c++)
			{
				if(i<bn && b[i+1]==c) goT[i][c]=i+1;
				else goT[i][c]=goT[k][c];
			}
		}
		
		int ok=0;
		
		memset(f,0,sizeof f);
		f[0][0][0][0]=1;
		queue< tuple<int,int,int,int> >q;
		q.emplace(0,0,0,0);
		while(!q.empty())
		{
			const auto [u,i,v,j]=q.front(); q.pop();
			for(int c=0;c<2;c++)
			{
				int ni=goS[i][c],nj=goT[j][c];
				int nu=u+(ni==an),nv=v+(nj==bn);
				if(nu==0&&nv==1) continue;
				
				if( nu<=2 && nv<=1 && !f[nu][ni][nv][nj] )
				{
					f[nu][ni][nv][nj]=1;
					q.emplace(nu,ni,nv,nj);
				}
			}
		}
		{
			int cc=1;
			for(int i=0;i<=an;i++) for(int j=0;j<=bn;j++) if(f[2][i][0][j])
			{
				cc=0;
			}
			if(cc) ok=1;
		}
		
		
		memset(f,0,sizeof f);
		f[0][0][0][0]=1;
		q.emplace(0,0,0,0);
		while(!q.empty())
		{
			const auto [u,i,v,j]=q.front(); q.pop();
			for(int c=0;c<2;c++)
			{
				int ni=goS[i][c],nj=goT[j][c];
				int nu=u+(ni==an),nv=v+(nj==bn);
				if(nu==1&&nv==0) continue;
				
				if( nu<=1 && nv<=2 && !f[nu][ni][nv][nj] )
				{
					f[nu][ni][nv][nj]=1;
					q.emplace(nu,ni,nv,nj);
				}
			}
		}
		{
			int cc=1;
			for(int i=0;i<=an;i++) for(int j=0;j<=bn;j++) if(f[0][i][2][j])
			{
				cc=0;
			}
			if(cc) ok=1;
		}
		
		cout<<ok<<'\n';
	}
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 12380kb

input:

3
ab ab ba
abc ab ba
cz cczz zzcc

output:

1
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

7
d d d
d dd d
d d dd
z zzzzzzzzzzzz zzz
a aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1
1
1
1
1
1
1

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 12372kb

input:

10
ab aaaaaabbabbbbb bbbbba
ab aaaaaabbabbbbb baaaaaa
ab aaaaaabbabbbbb bbbba
ab aaaaaabbabbbbb bbba
ab aaaaaabbabbbbb baaa
ab aaaaaabbabbbbb baaaaa
ab aaaaaabbabbbbb baa
ab aaaaaabbabbbbb baaaa
ab aaaaaabbabbbbb baaaaaaa
ab aaaaaabbabbbbb bbbbbba

output:

1
1
1
1
1
1
1
1
0
0

result:

ok 10 lines

Test #4:

score: 0
Accepted
time: 45ms
memory: 12380kb

input:

50
az aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

50
az aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 50 lines

Test #6:

score: 0
Accepted
time: 47ms
memory: 12444kb

input:

50
az zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #7:

score: 0
Accepted
time: 40ms
memory: 12388kb

input:

50
az azaaaaaaazaazzzzazzzaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #8:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

50
az zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 50 lines

Test #9:

score: 0
Accepted
time: 46ms
memory: 12392kb

input:

50
az zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #10:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

50
az aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 50 lines

Test #11:

score: 0
Accepted
time: 15ms
memory: 12372kb

input:

50
az aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

50
ab bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 50 lines

Test #13:

score: 0
Accepted
time: 4ms
memory: 3428kb

input:

50
icp cppcpccpiccccccppiiiipicpcipicciciciccipcpcccpipcpppcipicipiipppipccppppiiippcpcpiciipcpipiipcccpiciiiicpipipcpcpicccpicppcciicippipcpicippcipppcppciiccicipccppccpccpipciipiippciippppicccciiicpciicpcppcipcippcppccipipcppcccppppciiccpippcipiipciccciccccccppipcccccicicpcppippciiccpiccppppccippc...

output:

0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #14:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

50
oks kksksoskssksskssksoksoskkkoooskkskskkkkkkokssksokoskkksooskkkokkkksosssoksskokokoksooosksskkkosssosoooskssokkooossskssssosossksoookkss koskskkkksssskkoossosskkskoskokokooksokossssokookkokosssoosoosskksokskskokkokokosookksokksokokooskokokkkkookosokooosoosksksoskkoookoskksksoskskssskoskskkkkskk...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 50 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

50
swxyrcjgp jjxypwcpgjxxcwccgwpsyxgjpwrgwpxwywwwxsxsyyygypwjrwpgcxgcgpgrrjwgjgpjsswjwpsjyxxyxscwcsxysywwyspgrspjsxypyyxsgyssswrcrpjgrygxwgjcyppysycpxyjjjgrgyxcwyywsrpyccrryprcjwgswrcjjgjxwyrpsgjpccrjwsjwxgjpsjssjycxxjprycxjxrpwgxcpjycwxyrgpppwwjjjcjrjxssxwyryxjyjjyjcjcsjsccpxxgscsspsryrjswpcwjgspsx...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1

result:

ok 50 lines

Test #16:

score: 0
Accepted
time: 0ms
memory: 12376kb

input:

1
az aaaaza azaaaa

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 42ms
memory: 12376kb

input:

50
ab aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 50 lines