QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#640181 | #80. Gluing Pictures | EldoSantos | AC ✓ | 71ms | 7528kb | C++14 | 3.4kb | 2024-10-14 08:44:58 | 2024-10-14 08:45:00 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define pb push_back
#define ll long long
#define s second
#define f first
#define MOD 1000000007
#define INF 1000000000
using i64 = long long;
struct SuffixArray
{
int n;
std::vector<int> sa, rk, lc;
SuffixArray(const std::string &s)
{
n = s.length();
sa.resize(n);
lc.resize(n - 1);
rk.resize(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int a, int b)
{ return s[a] < s[b]; });
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
int k = 1;
std::vector<int> tmp, cnt(n);
tmp.reserve(n);
while (rk[sa[n - 1]] < n - 1)
{
tmp.clear();
for (int i = 0; i < k; ++i)
tmp.push_back(n - k + i);
for (auto i : sa)
if (i >= k)
tmp.push_back(i - k);
std::fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; ++i)
++cnt[rk[i]];
for (int i = 1; i < n; ++i)
cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i)
sa[--cnt[rk[tmp[i]]]] = tmp[i];
std::swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
k *= 2;
}
for (int i = 0, j = 0; i < n; ++i)
{
if (rk[i] == 0)
{
j = 0;
}
else
{
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j];)
++j;
lc[rk[i] - 1] = j;
}
}
}
};
void solve(){
string str;cin>>str;
SuffixArray sa(str);
set<char> alf;
for(auto u:str){
alf.insert(u);
}
int n;cin>>n;
for(int i=0;i<n;i++){
string si;cin>>si;
bool x=0;
for(auto u:si){
if(alf.count(u)==0){
cout<<-1<<endl;
x=1;
break;
}
}
if(x)continue;
int ans=0;
bool d1=1;
int poi=0;
while(si.size()>poi){
int l=-1,r=str.size()-1;
while(r-l>1){
int m1=l+(r-l)/2;
bool d=str.size()-sa.sa[m1]>=(si.size()-poi);
for(int j=sa.sa[m1];j<str.size()&&j-sa.sa[m1]<(si.size()-poi);j++){
if(str[j]!=si[poi+j-sa.sa[m1]]){
d=str[j]>si[poi+j-sa.sa[m1]];
break;
}
}
if(d){
r=m1;
}
else{
l=m1;
}
}
int f=0;
for(int j=max(0,r-1);j<=min(r,int(str.size()-1));j++){
int actual=0;
for(int k=sa.sa[j];k<str.size()&&k-sa.sa[j]<(si.size()-poi);k++){
if(str[k]==si[poi+k-sa.sa[j]]){
actual++;
}
else{
break;
}
}
f=max(f,actual);
}
if(f==0){
d1=0;
break;
}
poi+=f;
ans++;
}
if(d1){
cout<<ans<<endl;
}
else{
cout<<-1<<endl;
}
}
// cout<<3232<<endl;
// for(int i=0;i<str.size();i++){
// cout<<sa.sa[i]<<endl;
// }
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//int t;cin>>t;for(int T=0;T<t;T++)
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
MONTEVIDEO 4 DEMONIO MONTE EDIT WON
output:
4 1 4 -1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 25ms
memory: 7528kb
input:
PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 71ms
memory: 3652kb
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: 3584kb
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: 3884kb
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: 3692kb
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: 3648kb
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: 3660kb
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: 3652kb
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: 21ms
memory: 5352kb
input:
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...
output:
99999
result:
ok single line: '99999'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3636kb
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: 3648kb
input:
SANTIAGO 3 TITA SANTIAGO NAS
output:
3 1 3
result:
ok 3 lines
Test #13:
score: 0
Accepted
time: 25ms
memory: 6052kb
input:
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
364
result:
ok single line: '364'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3696kb
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: 3920kb
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: 12ms
memory: 4644kb
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: 3ms
memory: 3804kb
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: 9ms
memory: 4816kb
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: 3ms
memory: 3924kb
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: 2ms
memory: 3772kb
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: 1ms
memory: 3780kb
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: 3712kb
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: 1ms
memory: 3624kb
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: 3764kb
input:
A 1 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
-1
result:
ok single line: '-1'