QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235493 | #7697. Impartial Strings | PhantomThreshold# | AC ✓ | 47ms | 12444kb | C++20 | 3.0kb | 2023-11-02 20:21:08 | 2023-11-02 20:21:09 |
Judging History
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