QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#808269 | #80. Gluing Pictures | LaVuna47# | AC ✓ | 69ms | 39780kb | C++17 | 3.4kb | 2024-12-10 19:13:03 | 2024-12-10 19:13:03 |
Judging History
answer
/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
struct SuffixAutomaton {
struct State {
int len, link;
std::map<char, int> transitions;
};
std::vector<State> states;
int last;
SuffixAutomaton(const std::string& s) {
states.reserve(2 * s.size());
states.push_back({0, -1}); // Initial state
last = 0;
for (char c : s)
add_char(c);
}
void add_char(char c) {
int cur = states.size();
states.push_back({states[last].len + 1, -1});
int p = last;
while (p != -1 && !states[p].transitions.count(c)) {
states[p].transitions[c] = cur;
p = states[p].link;
}
if (p == -1) {
states[cur].link = 0;
} else {
int q = states[p].transitions[c];
if (states[p].len + 1 == states[q].len) {
states[cur].link = q;
} else {
int clone = states.size();
states.push_back(states[q]);
states[clone].len = states[p].len + 1;
while (p != -1 && states[p].transitions[c] == q) {
states[p].transitions[c] = clone;
p = states[p].link;
}
states[q].link = states[cur].link = clone;
}
}
last = cur;
}
int query(const std::string& t)
{
int current_state = 0;
int ctr=1;
for (char c : t)
{
if (!states[current_state].transitions.count(c))
{
++ctr;
current_state=0;
}
current_state = states[current_state].transitions[c];
}
return ctr;
}
};
int solve()
{
string W;
if(!(cin>>W))return 1;
SuffixAutomaton sa(W);
bool there[26]{};
for(auto& ch: W)
there[ch-'A']=true;
int n;
cin>>n;
vector<string> s(n);
FOR(i,0,n)cin>>s[i];
for(auto& str: s)
{
bool ok=true;
for(auto ch:str)
{
if(!there[ch-'A'])ok=false;
}
cout << (ok ? sa.query(str) : -1) << '\n';
}
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
MONTEVIDEO 4 DEMONIO MONTE EDIT WON
output:
4 1 4 -1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 69ms
memory: 39780kb
input:
PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 12ms
memory: 9312kb
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: 0ms
memory: 3640kb
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: 3608kb
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: 3672kb
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: 3632kb
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: 0ms
memory: 3636kb
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: 0ms
memory: 3640kb
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: 13832kb
input:
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...
output:
99999
result:
ok single line: '99999'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3832kb
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: 0ms
memory: 3808kb
input:
SANTIAGO 3 TITA SANTIAGO NAS
output:
3 1 3
result:
ok 3 lines
Test #13:
score: 0
Accepted
time: 7ms
memory: 30876kb
input:
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
364
result:
ok single line: '364'
Test #14:
score: 0
Accepted
time: 2ms
memory: 4200kb
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: 2ms
memory: 4164kb
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: 10304kb
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: 0ms
memory: 4620kb
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: 25ms
memory: 19868kb
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: 6ms
memory: 11568kb
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: 7416kb
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: 0ms
memory: 5240kb
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: 4224kb
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: 0ms
memory: 3664kb
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: 1ms
memory: 3992kb
input:
A 1 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1
result:
ok single line: '-1'