QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #244120 | #7697. Impartial Strings | SolitaryDream# | WA | 1128ms | 9552kb | C++17 | 2.1kb | 2023-11-08 21:22:16 | 2023-11-08 21:22:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
const int N=1005;
int tag[26];
int ch[N][26];
int fail[N];
int tid;
int ins() {
string s;
cin >> s;
int p=0;
for(auto c: s) {
c-='a';
if(!ch[p][c]) ch[p][c]=++tid;
p=ch[p][c];
}
return p;
}
int Q[N*N*2];
int dis[N];
int mark[N];
int cnt[N];
void solve() {
string cc;
cin >> cc;
memset(tag,0,sizeof(tag));
for(auto c: cc) tag[c-'a']=1;
memset(ch,0,sizeof(ch));
memset(fail,0,sizeof(fail));
tid=0;
int p[2];
p[0]=ins();
p[1]=ins();
int l=1,r=0;
FOR(i,0,25) if(tag[i] && ch[0][i]) Q[++r]=ch[0][i];
while(l<=r) {
int p=Q[l++];
FOR(i,0,25) if(tag[i]) {
if(ch[p][i]) {
Q[++r]=ch[p][i];
fail[ch[p][i]]=ch[fail[p]][i];
} else ch[p][i]=ch[fail[p]][i];
}
}
// FOR(i,0,tid) FOR(j,0,25) if(tag[j]) cerr << i << ' ' << ch[i][j] << '\n';
// cerr << p[0] << ' ' << p[1] << endl;
int res=0;
FOR(_,0,1) {
for(int i=0;i<=tid;i++)dis[i]=-1e9;
memset(mark,0,sizeof(mark));
memset(cnt,0,sizeof(cnt));
l=1,r=0;
dis[0]=0;
Q[++r]=0;
mark[0]=1;
while(l<=r) {
int x=Q[l++];
++cnt[x];
if(cnt[x]>tid+5) {
// cerr << _ << endl;
++res;
break;
}
mark[x]=0;
FOR(i,0,25) if(tag[i]) {
int y=ch[x][i];
if(dis[x]+(y==p[_])-(y==p[_^1])>dis[y]) {
// cerr << dis[y] << endl;
dis[y]=dis[x]+(y==p[_])-(y==p[_^1]);
if(!mark[y]) {
Q[++r]=y;
mark[y]=1;
}
}
}
}
}
cout << (res<2) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
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: 1ms
memory: 3740kb
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: 1ms
memory: 3732kb
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: 1128ms
memory: 9552kb
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: -100
Wrong Answer
time: 181ms
memory: 6868kb
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 1
result:
wrong answer 1st lines differ - expected: '1', found: '0'