QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#147411 | #80. Gluing Pictures | kanner9 | AC ✓ | 72ms | 46460kb | C++14 | 3.2kb | 2023-08-23 07:09:16 | 2023-08-25 01:29:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define fl(i, a, b) for (int i = a; i < b; ++i)
#define all(v) (v).begin(), (v).end()
#define srt(v) sort(all(v))
#define pb push_back
#define mp make_pair
#define dig(i) (s[i] - '0')
#define slen(s) s.length()
#define fr first
#define sc second
#define len(x) x.size()
#define fill(x, y) memset(x, y, sizeof(x))
#define clr(a) fill(a, 0)
#define endl '\n'
#define PI 3.14159265358979323
#define trace1(x1) cerr << #x1 << ": " << x1 << endl;
#define trace2(x1, x2) \
cerr << #x1 << ": " << x1 << " | " << #x2 << ": " << x2 << endl;
#define trace3(x1, x2, x3) \
cerr << #x1 << ": " << x1 << " | " << #x2 << ": " << x2 << " | " << #x3 \
<< ": " << x3 << endl;
#define FAST_IO \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
const ll MOD = 1000000007LL;
const ll MAX = 100010LL;
template <typename T>
T gcd(T a, T b) {
if (b == 0) return a;
return gcd(b, a % b);
}
template <typename T>
T power(T x, T y, ll m = MOD) {
T ans = 1;
x %= m;
while (y > 0) {
if (y & 1ll) ans = (ans * x) % m;
y >>= 1ll;
x = (x * x) % m;
}
return ans % m;
}
struct state {
int len, link;
map<char, int> next;
};
const int MAXLEN = 200001;
state st[MAXLEN * 2];
int sz, last;
void sa_init() {
st[0].len = 0;
st[0].link = -1;
sz++;
last = 0;
}
void sa_extend(char& c) {
int cur = sz++;
st[cur].len = st[last].len + 1;
int p = last;
while (p != -1 && !st[p].next.count(c)) {
st[p].next[c] = cur;
p = st[p].link;
}
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) {
st[cur].link = q;
} else {
int clone = sz++;
st[clone].len = st[p].len + 1;
st[clone].next = st[q].next;
st[clone].link = st[q].link;
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
// Find if T is a substring of S
int isSubString(string& T) {
int ans = 0, cur = 0;
for (int i = 0; i < T.length(); i++) {
if (st[cur].next.count(T[i])) {
cur = st[cur].next[T[i]];
}
else if(cur == 0){
return -1;
}
else {
ans++;
i--;
cur = 0;
}
}
cur = 0;
if (st[cur].next.count(T[T.length()-1])) {
ans++;
}
return ans;
}
int main() {
FAST_IO;
string C, T;
int N, ans, flag;
while (cin >> C) {
cin >> N;
sa_init();
for (int i = 0; i < C.length(); i++) sa_extend(C[i]);
for (int i = 0; i < N; i++) {
cin >> T;
string S = "";
ans = 0;
flag = 0;
cout<<isSubString(T)<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 25332kb
input:
MONTEVIDEO 4 DEMONIO MONTE EDIT WON
output:
4 1 4 -1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 72ms
memory: 46460kb
input:
PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 14ms
memory: 25444kb
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: 1ms
memory: 25400kb
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: 25372kb
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: 2ms
memory: 25416kb
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: 0ms
memory: 25352kb
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: 25344kb
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: 8ms
memory: 25404kb
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: 4ms
memory: 30360kb
input:
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...
output:
99999
result:
ok single line: '99999'
Test #11:
score: 0
Accepted
time: 3ms
memory: 25496kb
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: 4ms
memory: 25448kb
input:
SANTIAGO 3 TITA SANTIAGO NAS
output:
3 1 3
result:
ok 3 lines
Test #13:
score: 0
Accepted
time: 10ms
memory: 37996kb
input:
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
364
result:
ok single line: '364'
Test #14:
score: 0
Accepted
time: 10ms
memory: 25964kb
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: 1ms
memory: 26012kb
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: 3ms
memory: 28668kb
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: 2ms
memory: 25844kb
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: 20ms
memory: 34664kb
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: 8ms
memory: 29976kb
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: 5ms
memory: 27656kb
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: 6ms
memory: 26552kb
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: 3ms
memory: 25992kb
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: 2ms
memory: 25372kb
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: 8ms
memory: 25580kb
input:
A 1 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1
result:
ok single line: '-1'