QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53953#80. Gluing Picturesnot_so_organicAC ✓37ms47756kbC++201.7kb2022-10-06 13:38:082022-10-06 13:38:09

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 13:38:09]
  • Judged
  • Verdict: AC
  • Time: 37ms
  • Memory: 47756kb
  • [2022-10-06 13:38:08]
  • Submitted

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'