QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244089#7697. Impartial StringsSolitaryDream#WA 1133ms8764kbC++172.2kb2023-11-08 21:01:492023-11-08 21:01:50

Judging History

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

  • [2023-11-08 21:01:50]
  • 评测
  • 测评结果:WA
  • 用时:1133ms
  • 内存:8764kb
  • [2023-11-08 21:01:49]
  • 提交

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,flag=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[p[_]]=0;
        Q[++r]=p[_];
        mark[p[_]]=1;
        while(l<=r) {
            int x=Q[l++];
            mark[x]=0;
            ++cnt[x];
            if(cnt[x]>tid+5) {
                continue;
            }
            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;
                    }
                }
            }
        }
        FOR(i,0,tid) if(cnt[i]>tid+5) {
            res++;
            break;
        }
        if(cnt[p[_^1]]) flag=1;
    }
    cout << (res<2 || !flag) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3740kb

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: 3636kb

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: 3716kb

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: 1133ms
memory: 8764kb

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: 208ms
memory: 4708kb

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'