QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53953 | #80. Gluing Pictures | not_so_organic | AC ✓ | 37ms | 47756kb | C++20 | 1.7kb | 2022-10-06 13:38:08 | 2022-10-06 13:38:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace::std;
const int N = 200000 + 5;
const int SUML = 2 * N;
const int E = 26;
struct node{
int len;
int link;
int next[E];
node(){
memset(next, 0, sizeof next);
}
};
int q;
int last;
int nodes;
char s[SUML];
node sa[SUML];
void sa_init(){
sa[nodes].len = 0;
sa[nodes].link = -1;
last = nodes++;
}
int clone_node(int p, int q){
int clone = nodes++;
sa[clone].len = sa[p].len + 1;
sa[clone].link = sa[q].link;
for(int i = 0; i < E; i++) sa[clone].next[i] = sa[q].next[i];
return clone;
}
void sa_extend(int c){
int cur = nodes++;
sa[cur].len = sa[last].len + 1;
int p = last;
while(p != -1 and sa[p].next[c] == 0){
sa[p].next[c] = cur;
p = sa[p].link;
}
if(p == -1){
sa[cur].link = 0;
}
else{
int q = sa[p].next[c];
if(sa[p].len + 1 == sa[q].len){
sa[cur].link = q;
}
else{
int clone = clone_node(p, q);
while(p != -1 and sa[p].next[c] == q){
sa[p].next[c] = clone;
p = sa[p].link;
}
sa[q].link = sa[cur].link = clone;
}
}
last = cur;
}
void build_automaton(){
sa_init();
for(int i = 0; s[i]; i++){
int x = s[i] - 'A';
sa_extend(x);
}
}
int solve(){
int pos = 0;
int ans = 0;
for(int i = 0; s[i]; i++){
int c = s[i] - 'A';
if(sa[pos].next[c]){
pos = sa[pos].next[c];
continue;
}
if(sa[pos].next[c] == 0){
pos = 0;
ans++;
}
if(sa[pos].next[c] == 0) return -1;
pos = sa[pos].next[c];
}
ans += pos > 0;
return ans;
}
int main(){
scanf("%s", s);
build_automaton();
scanf("%d", &q);
while(q--){
scanf("%s", s);
printf("%d\n", solve());
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 13ms
memory: 47600kb
input:
MONTEVIDEO 4 DEMONIO MONTE EDIT WON
output:
4 1 4 -1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 19ms
memory: 47720kb
input:
PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 37ms
memory: 47532kb
input:
A 199999 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A...
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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 199999 lines
Test #4:
score: 0
Accepted
time: 4ms
memory: 47488kb
input:
BGTIWPXFVZAUS 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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
result:
ok 26 lines
Test #5:
score: 0
Accepted
time: 3ms
memory: 47448kb
input:
ADVXIFPRSUQHC 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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
result:
ok 26 lines
Test #6:
score: 0
Accepted
time: 17ms
memory: 47560kb
input:
FCERYGBJXKSIT 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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
result:
ok 26 lines
Test #7:
score: 0
Accepted
time: 3ms
memory: 47444kb
input:
VSHZPYTLRXKDO 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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
result:
ok 26 lines
Test #8:
score: 0
Accepted
time: 9ms
memory: 47520kb
input:
FQZMJLPDSOXAK 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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
result:
ok 26 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 47448kb
input:
TNHHGYVHFKSDSMH 8 VHFKS DSNHHGYVHFTNFKSD TNNHHGYNHHTN HGVVHFKSDSGYV HFKSTNHHGYVTNHFKSHHGY VHSDSMHKSSDSM H HGYVHFKHHGYVHNHHHGY
output:
1 4 4 4 5 4 1 4
result:
ok 8 lines
Test #10:
score: 0
Accepted
time: 12ms
memory: 47608kb
input:
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...
output:
99999
result:
ok single line: '99999'
Test #11:
score: 0
Accepted
time: 3ms
memory: 47564kb
input:
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAAB...
output:
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 2038 lines
Test #12:
score: 0
Accepted
time: 8ms
memory: 47388kb
input:
SANTIAGO 3 TITA SANTIAGO NAS
output:
3 1 3
result:
ok 3 lines
Test #13:
score: 0
Accepted
time: 15ms
memory: 47732kb
input:
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
364
result:
ok single line: '364'
Test #14:
score: 0
Accepted
time: 7ms
memory: 47532kb
input:
ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXKIIIKJKJJJJJKKLXIJLJJKJLIKJKJJLXKKIHIIKKKIKJJJIXIKHKJJKIJJLJJJJXIJIHKIJIKIKIKIJXJJIJJJJJJJIMJJJXIIJJKJIJKIHIJKHXJJKKKJHJJLKHJIJXIJJIKKKIIILHIJJXKIKJIKIKJKIJHJJXKJKIKJGKJHKKKJIXKHHLIJJIKILJIKIXIK...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 300 lines
Test #15:
score: 0
Accepted
time: 16ms
memory: 47512kb
input:
ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXJLIJJKLJJJJJKIJXKKJIIJIJLIJJJMKXIILHKIJIJJJKJILXLKHKJJJJKJKIJKKXMJJIJJJKIKJLKJKXIJJJJJJJIKJJJJJXKJJJGJJIKIIILJKXKJIHJILIJIJJJHJXJIJKLKIKHJKJIKKXIJIKHKJJIIKIKJIXJJLJKHKJJJJIHLJXKJIJLJIIJJIJKKJXJJ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 300 lines
Test #16:
score: 0
Accepted
time: 9ms
memory: 47624kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok 17 lines
Test #17:
score: 0
Accepted
time: 9ms
memory: 47616kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
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 1 1 1 1 1 1 1 1 1 1
result:
ok 60 lines
Test #18:
score: 0
Accepted
time: 22ms
memory: 47516kb
input:
ABABBBAABABBBAAABAAABAAABBABBAAAABAABBBBBABBBABABBAABBBBABAABABABAAABAABAABABBBABBAAAAAAAAABBBBAABBAABAAABAABABABBABABABAABAAAABBBBBBABBABAABBAABBBABAABBBAABAABABBABBABABABBAABBBBAABABBBAABABBBBAAABBBBAABBABABABAABAAABBAAABABAABBAABAAABABBABBBAABBABAABAABBBBBABABBBBABABAABAABABBABAABBBBABBBABBBAAABB...
output:
149 524 2 112 282 40 42 143 350 1247 581 164 369 410 457 238 171 17 386 210
result:
ok 20 lines
Test #19:
score: 0
Accepted
time: 13ms
memory: 47532kb
input:
BABBABABBABABBBAABBAAABBABBBBBBBABBAABBABAABBAAABBABBBABAAAABAAAABABABBAABAAAABAAABAABABAAAAABBBABABBAABABAABABBABAABABBAAABABABAAABABBAABBBABBAABBABBBBAAAAAABBBAABABBBAAABBBBBABBBAABBBABBABBAAAAAAABABAAAABAABAAABAAABAABAAABABBABBAAAABBBAABBBBABAAABAABBBABAAABBAAAABBABAABABBABBABABABAAAAAABAAABBAABA...
output:
1 2 1 2 1 1 1 1 1 1 1 4 1 1 2 3 2 3 2 1 1 1 2 1 2 2 1 4 2 1 3 2 4 1 3 3 2 1 1 3 2 1 1 1 1 3 1 1 4 1 1 1 2 3 4 1 2 7 1 1 1 3 1 1 2 2 1 1 3 1 1 4 2 3 1 1 1 2 1 4 1 1 1 1 1 4 2 1 3 1 2 1 2 1 2 1 3 3 1 1
result:
ok 100 lines
Test #20:
score: 0
Accepted
time: 16ms
memory: 47544kb
input:
AAABAABBABBAAAAAABBBABAAABABBBBBAABAABBBABAABBBABBBAABBBBBBABBABBBBBBBAABAABBBBBAABAAAAAABABABAAABAABBABBABBAAABABAABBAAAABABABAAAAABAABBAABABABAAAABABAABBAABBAABAABABABBAAABAAABBABBBABBABAABBAABBBBABABAAAABBAAAABAAAAABBBAAAABBBBABBBBAABAAABAABBAAAABBBABAAAAAAABBABAAABBBABBBABAABBBAABAAAABBABBABAAAA...
output:
3 1 2 2 1 2 5 1 1 2 1 1 1 1 1 1 4 1 4 2 1 2 2 1 2 1 3 1 2 3 1 1 4 1 3 1 2 1 3 1 1 1 2 1 1 4 1 2 3 1 1 1 1 1 2 1 3 1 3 1 1 4 1 2 3 1 3 3 2 1 2 1 1 2 2 2 1 5 2 2 3 6 2 1 1 2 1 2 2 4 3 2 3 1 3 1 1 1 1 1
result:
ok 100 lines
Test #21:
score: 0
Accepted
time: 11ms
memory: 47456kb
input:
AABAAAAAAAAAABBBAABABBAABBAAABAABAAAABBBAAABAABBBBBABBBAAABABAAABBABAABBBBBABBAABAAABBAABBABAABBAABAAABBBABBBABBBABBAABBBAABABBBBBBAAABBAABAAABBABBAAABAABAABBBBABBAAAABABAAABBBBBAAAABBAAABABABBAABBBAABBAAAAABBAAABABBBBBBBAAAAABABABBABAABBBABBABBABBABAABABBABABAAAABABBBBBBAABABBABABABABAABBBBBBBBBABB...
output:
2 2 3 1 3 1 2 1 2 2 2 1 2 2 1 1 1 1 1 1 1 1 1 3 3 1 3 2 3 2 1 1 1 1 3 4 1 4 1 1 1 5 2 1 1 2 2 2 1 1 1 1 4 1 1 4 1 1 1 6 6 2 2 1 1 2 2 1 2 4 2 1 4 4 2 1 4 1 1 1 1 1 3 2 3 3 2 3 2 1 4 5 1 1 2 2 4 1 1 1
result:
ok 100 lines
Test #22:
score: 0
Accepted
time: 1ms
memory: 47524kb
input:
BBBBAAABAAABABABABABAABAABBABBBABBABAAAABBABABBBABABABBABBBBBBABAABBABBAABBAAABBBBBBABAAABBABBABBABBBAABBABABBBBBBABABBBAAABAABBAAAABBAABBAAAAAABBABBAAABBAABBAABABBBAAABABBABBBABABBBABBBBBABAAABAAAABBBAABAAABBBAABAABAAABBABAAABBBBAABABBABABBABBBBAAABAABBBBBAAABBABABBAAABBAAABBABAABAAABAAABBBAAABABAA...
output:
1 1 4 4 1 1 3 1 3 1 1 2 1 1 1 1 1 1 2 1 1 2 2 1 1 2 1 5 1 2 3 2 1 2 1 1 2 2 1 1 6 1 2 4 2 2 1 4 2 3 2 3 1 6 1 2 1 1 3 4 3 1 1 1 1 4 2 1 10 4 1 1 1 1 2 1 1 1 3 2 2 2 1 1 1 2 3 1 1 1 2 4 2 2 2 4 3 1 1 3
result:
ok 100 lines
Test #23:
score: 0
Accepted
time: 9ms
memory: 47520kb
input:
A 100 A AA AAA AAAA AAAAA AAAAAA AAAAAAA AAAAAAAA AAAAAAAAA AAAAAAAAAA AAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAAA AAAAAAAAAAAAAA AAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAA...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
result:
ok 100 lines
Test #24:
score: 0
Accepted
time: 11ms
memory: 47756kb
input:
A 1 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1
result:
ok single line: '-1'