QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#32270	#80. Gluing Pictures	querqqq	AC ✓	19ms	38916kb	C++	1.4kb	2022-05-18 16:03:26	2022-05-18 16:03:27

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-05-18 16:03:27]
评测

测评结果：AC
用时：19ms
内存：38916kb

查看

[2022-05-18 16:03:26]
提交

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++

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 12040kb

input:

MONTEVIDEO
4
DEMONIO
MONTE
EDIT
WON

output:

result:

ok 4 lines

Test #2:

score: 0

Accepted

time: 19ms

memory: 36904kb

input:

PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 17ms

memory: 11976kb

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

memory: 11980kb

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

memory: 11840kb

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

memory: 11956kb

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

memory: 12000kb

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

memory: 11956kb

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

input:

TNHHGYVHFKSDSMH
8
VHFKS
DSNHHGYVHFTNFKSD
TNNHHGYNHHTN
HGVVHFKSDSGYV
HFKSTNHHGYVTNHFKSHHGY
VHSDSMHKSSDSM
H
HGYVHFKHHGYVHNHHHGY

output:

result:

ok 8 lines

Test #10:

score: 0

Accepted

time: 3ms

memory: 21100kb

input:

ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...

output:

result:

ok single line: '99999'

Test #11:

score: 0

Accepted

time: 2ms

memory: 12084kb

input:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAAB...

output:

result:

ok 2038 lines

Test #12:

score: 0

Accepted

time: 4ms

memory: 12044kb

input:

SANTIAGO
3
TITA
SANTIAGO
NAS

output:

3
1
3

result:

ok 3 lines

Test #13:

score: 0

Accepted

time: 7ms

memory: 38916kb

input:

ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

result:

ok single line: '364'

Test #14:

score: 0

Accepted

time: 5ms

memory: 12292kb

input:

ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXKIIIKJKJJJJJKKLXIJLJJKJLIKJKJJLXKKIHIIKKKIKJJJIXIKHKJJKIJJLJJJJXIJIHKIJIKIKIKIJXJJIJJJJJJJIMJJJXIIJJKJIJKIHIJKHXJJKKKJHJJLKHJIJXIJJIKKKIIILHIJJXKIKJIKIKJKIJHJJXKJKIKJGKJHKKKJIXKHHLIJJIKILJIKIXIK...

output:

result:

ok 300 lines

Test #15:

score: 0

Accepted

time: 5ms

memory: 12016kb

input:

ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXJLIJJKLJJJJJKIJXKKJIIJIJLIJJJMKXIILHKIJIJJJKJILXLKHKJJJJKJKIJKKXMJJIJJJKIKJLKJKXIJJJJJJJIKJJJJJXKJJJGJJIKIIILJKXKJIHJILIJIJJJHJXJIJKLKIKHJKJIKKXIJIKHKJJIIKIKJIXJJLJKHKJJJJIHLJXKJIJLJIIJJIJKKJXJJ...

output:

result:

ok 300 lines

Test #16:

score: 0

Accepted

time: 7ms

memory: 17280kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

result:

ok 17 lines

Test #17:

score: 0

Accepted

time: 7ms

memory: 12056kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

result:

ok 60 lines

Test #18:

score: 0

Accepted

time: 18ms

memory: 25156kb

input:

ABABBBAABABBBAAABAAABAAABBABBAAAABAABBBBBABBBABABBAABBBBABAABABABAAABAABAABABBBABBAAAAAAAAABBBBAABBAABAAABAABABABBABABABAABAAAABBBBBBABBABAABBAABBBABAABBBAABAABABBABBABABABBAABBBBAABABBBAABABBBBAAABBBBAABBABABABAABAAABBAAABABAABBAABAAABABBABBBAABBABAABAABBBBBABABBBBABABAABAABABBABAABBBBABBBABBBAAABB...

output:

result:

ok 20 lines

Test #19:

score: 0

Accepted

time: 3ms

memory: 17364kb

input:

BABBABABBABABBBAABBAAABBABBBBBBBABBAABBABAABBAAABBABBBABAAAABAAAABABABBAABAAAABAAABAABABAAAAABBBABABBAABABAABABBABAABABBAAABABABAAABABBAABBBABBAABBABBBBAAAAAABBBAABABBBAAABBBBBABBBAABBBABBABBAAAAAAABABAAAABAABAAABAAABAABAAABABBABBAAAABBBAABBBBABAAABAABBBABAAABBAAAABBABAABABBABBABABABAAAAAABAAABBAABA...

output:

result:

ok 100 lines

Test #20:

score: 0

Accepted

time: 3ms

memory: 13820kb

input:

AAABAABBABBAAAAAABBBABAAABABBBBBAABAABBBABAABBBABBBAABBBBBBABBABBBBBBBAABAABBBBBAABAAAAAABABABAAABAABBABBABBAAABABAABBAAAABABABAAAAABAABBAABABABAAAABABAABBAABBAABAABABABBAAABAAABBABBBABBABAABBAABBBBABABAAAABBAAAABAAAAABBBAAAABBBBABBBBAABAAABAABBAAAABBBABAAAAAAABBABAAABBBABBBABAABBBAABAAAABBABBABAAAA...

output:

result:

ok 100 lines

Test #21:

score: 0

Accepted

time: 0ms

memory: 12108kb

input:

AABAAAAAAAAAABBBAABABBAABBAAABAABAAAABBBAAABAABBBBBABBBAAABABAAABBABAABBBBBABBAABAAABBAABBABAABBAABAAABBBABBBABBBABBAABBBAABABBBBBBAAABBAABAAABBABBAAABAABAABBBBABBAAAABABAAABBBBBAAAABBAAABABABBAABBBAABBAAAAABBAAABABBBBBBBAAAAABABABBABAABBBABBABBABBABAABABBABABAAAABABBBBBBAABABBABABABABAABBBBBBBBBABB...

output:

result:

ok 100 lines

Test #22:

score: 0

Accepted

time: 4ms

memory: 11988kb

input:

BBBBAAABAAABABABABABAABAABBABBBABBABAAAABBABABBBABABABBABBBBBBABAABBABBAABBAAABBBBBBABAAABBABBABBABBBAABBABABBBBBBABABBBAAABAABBAAAABBAABBAAAAAABBABBAAABBAABBAABABBBAAABABBABBBABABBBABBBBBABAAABAAAABBBAABAAABBBAABAABAAABBABAAABBBBAABABBABABBABBBBAAABAABBBBBAAABBABABBAAABBAAABBABAABAAABAAABBBAAABABAA...

output:

result:

ok 100 lines

Test #23:

score: 0

Accepted

time: 4ms

memory: 11976kb

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

memory: 12748kb

input:

A
1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

-1

result:

ok single line: '-1'