QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#701410	#80. Gluing Pictures	TheZone	AC ✓	17ms	40020kb	C++20	1.6kb	2024-11-02 14:10:45	2024-11-02 14:10:47

Judging History

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

[2024-11-02 14:10:47]
评测

测评结果：AC
用时：17ms
内存：40020kb

查看

[2024-11-02 14:10:45]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int last, cnt;
int ch[maxn << 1][26], fa[maxn << 1], len[maxn << 1], siz[maxn << 1];
void ins(int c) {
	int p = last, np = ++cnt;
	last = np;
	len[np] = len[p] + 1;
	for (; p && !ch[p][c]; p = fa[p])ch[p][c] = np;
	if (!p)fa[np] = 1;
	else {
		int q = ch[p][c];
		if (len[p] + 1 == len[q])fa[np] = q;
		else {
			int nq = ++cnt; len[nq] = len[p] + 1;
			memcpy(ch[nq], ch[q], sizeof(ch[q]));
			fa[nq] = fa[q]; fa[q] = fa[np] = nq;
			for (; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
		}
	}
	siz[np] = 1;
}

char s[maxn], t[maxn];
int n, m, T;
int dp[maxn];
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	last = cnt = 1;
	for (int i = 1; i <= n; i++)
		ins(s[i] - 'A');
	scanf("%d", &T);
	while (T--) {
		scanf("%s", t + 1);
		m = strlen(t + 1);
		fill(dp, dp + m + 1, INF);
		int p = 1;
		dp[0] = 0;
		bool flg = 1;
		int tmp = 0;
		for (int i = 1; i <= m; i++) {
			int c = t[i] - 'A';
			//int tmp = 0;
			if (ch[p][c]) {
				tmp++;
				p = ch[p][c];
			}
			else {
				while (p && !ch[p][c])p = fa[p];
				if (p == 0 && !ch[p][c]) {
					flg = 0;
					break;
				}
				else {
					tmp = len[p] + 1;
					p = ch[p][c];
				}
			}
			dp[i] = min(dp[i], dp[i - tmp] + 1);
		}
		printf("%d\n", flg ? dp[m] : -1);
	}
	return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 8044kb

input:

MONTEVIDEO
4
DEMONIO
MONTE
EDIT
WON

output:

result:

ok 4 lines

Test #2:

score: 0

Accepted

time: 12ms

memory: 37688kb

input:

PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 17ms

memory: 7984kb

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:

result:

ok 199999 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 7952kb

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: 0ms

memory: 8084kb

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: 1ms

memory: 8084kb

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: 1ms

memory: 8080kb

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: 1ms

memory: 8040kb

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: 1ms

memory: 8040kb

input:

TNHHGYVHFKSDSMH
8
VHFKS
DSNHHGYVHFTNFKSD
TNNHHGYNHHTN
HGVVHFKSDSGYV
HFKSTNHHGYVTNHFKSHHGY
VHSDSMHKSSDSM
H
HGYVHFKHHGYVHNHHHGY

output:

result:

ok 8 lines

Test #10:

score: 0

Accepted

time: 0ms

memory: 21312kb

input:

ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...

output:

result:

ok single line: '99999'

Test #11:

score: 0

Accepted

time: 2ms

memory: 8384kb

input:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAAB...

output:

result:

ok 2038 lines

Test #12:

score: 0

Accepted

time: 1ms

memory: 8044kb

input:

SANTIAGO
3
TITA
SANTIAGO
NAS

output:

3
1
3

result:

ok 3 lines

Test #13:

score: 0

Accepted

time: 4ms

memory: 40020kb

input:

ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

result:

ok single line: '364'

Test #14:

score: 0

Accepted

time: 0ms

memory: 10380kb

input:

ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXKIIIKJKJJJJJKKLXIJLJJKJLIKJKJJLXKKIHIIKKKIKJJJIXIKHKJJKIJJLJJJJXIJIHKIJIKIKIKIJXJJIJJJJJJJIMJJJXIIJJKJIJKIHIJKHXJJKKKJHJJLKHJIJXIJJIKKKIIILHIJJXKIKJIKIKJKIJHJJXKJKIKJGKJHKKKJIXKHHLIJJIKILJIKIXIK...

output:

result:

ok 300 lines

Test #15:

score: 0

Accepted

time: 0ms

memory: 10852kb

input:

ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXJLIJJKLJJJJJKIJXKKJIIJIJLIJJJMKXIILHKIJIJJJKJILXLKHKJJJJKJKIJKKXMJJIJJJKIKJLKJKXIJJJJJJJIKJJJJJXKJJJGJJIKIIILJKXKJIHJILIJIJJJHJXJIJKLKIKHJKJIKKXIJIKHKJJIIKIKJIXJJLJKHKJJJJIHLJXKJIJLJIIJJIJKKJXJJ...

output:

result:

ok 300 lines

Test #16:

score: 0

Accepted

time: 3ms

memory: 15508kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

result:

ok 17 lines

Test #17:

score: 0

Accepted

time: 0ms

memory: 9084kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

result:

ok 60 lines

Test #18:

score: 0

Accepted

time: 4ms

memory: 26780kb

input:

ABABBBAABABBBAAABAAABAAABBABBAAAABAABBBBBABBBABABBAABBBBABAABABABAAABAABAABABBBABBAAAAAAAAABBBBAABBAABAAABAABABABBABABABAABAAAABBBBBBABBABAABBAABBBABAABBBAABAABABBABBABABABBAABBBBAABABBBAABABBBBAAABBBBAABBABABABAABAAABBAAABABAABBAABAAABABBABBBAABBABAABAABBBBBABABBBBABABAABAABABBABAABBBBABBBABBBAAABB...

output:

result:

ok 20 lines

Test #19:

score: 0

Accepted

time: 0ms

memory: 17916kb

input:

BABBABABBABABBBAABBAAABBABBBBBBBABBAABBABAABBAAABBABBBABAAAABAAAABABABBAABAAAABAAABAABABAAAAABBBABABBAABABAABABBABAABABBAAABABABAAABABBAABBBABBAABBABBBBAAAAAABBBAABABBBAAABBBBBABBBAABBBABBABBAAAAAAABABAAAABAABAAABAAABAABAAABABBABBAAAABBBAABBBBABAAABAABBBABAAABBAAAABBABAABABBABBABABABAAAAAABAAABBAABA...

output:

result:

ok 100 lines

Test #20:

score: 0

Accepted

time: 0ms

memory: 11604kb

input:

AAABAABBABBAAAAAABBBABAAABABBBBBAABAABBBABAABBBABBBAABBBBBBABBABBBBBBBAABAABBBBBAABAAAAAABABABAAABAABBABBABBAAABABAABBAAAABABABAAAAABAABBAABABABAAAABABAABBAABBAABAABABABBAAABAAABBABBBABBABAABBAABBBBABABAAAABBAAAABAAAAABBBAAAABBBBABBBBAABAAABAABBAAAABBBABAAAAAAABBABAAABBBABBBABAABBBAABAAAABBABBABAAAA...

output:

result:

ok 100 lines

Test #21:

score: 0

Accepted

time: 2ms

memory: 11696kb

input:

AABAAAAAAAAAABBBAABABBAABBAAABAABAAAABBBAAABAABBBBBABBBAAABABAAABBABAABBBBBABBAABAAABBAABBABAABBAABAAABBBABBBABBBABBAABBBAABABBBBBBAAABBAABAAABBABBAAABAABAABBBBABBAAAABABAAABBBBBAAAABBAAABABABBAABBBAABBAAAAABBAAABABBBBBBBAAAAABABABBABAABBBABBABBABBABAABABBABABAAAABABBBBBBAABABBABABABABAABBBBBBBBBABB...

output:

result:

ok 100 lines

Test #22:

score: 0

Accepted

time: 0ms

memory: 8856kb

input:

BBBBAAABAAABABABABABAABAABBABBBABBABAAAABBABABBBABABABBABBBBBBABAABBABBAABBAAABBBBBBABAAABBABBABBABBBAABBABABBBBBBABABBBAAABAABBAAAABBAABBAAAAAABBABBAAABBAABBAABABBBAAABABBABBBABABBBABBBBBABAAABAAAABBBAABAAABBBAABAABAAABBABAAABBBBAABABBABABBABBBBAAABAABBBBBAAABBABABBAAABBAAABBABAABAAABAAABBBAAABABAA...

output:

result:

ok 100 lines

Test #23:

score: 0

Accepted

time: 1ms

memory: 5932kb

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:

result:

ok 100 lines

Test #24:

score: 0

Accepted

time: 0ms

memory: 8820kb

input:

A
1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

-1

result:

ok single line: '-1'