QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#147163 | #80. Gluing Pictures | kanner9 | TL | 102ms | 46640kb | C++ | 3.4kb | 2023-08-22 20:55:24 | 2023-08-22 20:55:26 |
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
bool isSubString(string& T) {
bool ans = true;
int cur = 0;
for (int i = 0; i < T.length() and ans; i++) {
if (st[cur].next.count(T[i])) {
cur = st[cur].next[T[i]];
} else {
ans = false;
}
}
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;
for (int j = 0; j < T.size() + 1 and !flag; j++) {
if (j < T.size()) S += T[j];
if (!isSubString(S)) {
if (len(S) == 1) flag = 1;
ans++;
if (j < T.size()) S = T[j];
} else if (j == T.size())
ans++;
}
if (flag)
cout << -1 << endl;
else
cout << ans << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 25516kb
input:
MONTEVIDEO 4 DEMONIO MONTE EDIT WON
output:
4 1 4 -1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 102ms
memory: 46640kb
input:
PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 22ms
memory: 25468kb
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: 2ms
memory: 25456kb
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: 25512kb
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: 0ms
memory: 25516kb
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: 25464kb
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: 4ms
memory: 25516kb
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: 25520kb
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: 11ms
memory: 30636kb
input:
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...
output:
99999
result:
ok single line: '99999'
Test #11:
score: 0
Accepted
time: 7ms
memory: 25672kb
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: 1ms
memory: 25464kb
input:
SANTIAGO 3 TITA SANTIAGO NAS
output:
3 1 3
result:
ok 3 lines
Test #13:
score: 0
Accepted
time: 58ms
memory: 38144kb
input:
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
364
result:
ok single line: '364'
Test #14:
score: 0
Accepted
time: 1ms
memory: 26316kb
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: 9ms
memory: 26044kb
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: -100
Time Limit Exceeded
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...