NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #197039 | #2723. 8.3t1 | tkswls | 100 | 100ms | 1840kb | C++11 | 980b | 2023-11-05 11:18:36 | 2023-11-05 12:08:38 |
answer
#include<bits/stdc++.h>
using namespace std;
int t, n, m, a[100005], b[100005];
vector<int> v[30];
string s, ss;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--) {
cin >> s >> ss;
n = s.size(), m = ss.size();
for (int i = 1; i <= n; i++) {
a[i] = s[i - 1] - 'a' + 1;
}
for (int i = 1; i <= m; i++) {
b[i] = ss[i - 1] - 'a' + 1;
}
for (int i = 1; i <= 26; i++) v[i].clear();
for (int i = 1; i <= n; i++) {
v[a[i]].push_back(i);
}
bool flg = false;
for (int i = 1; i <= m; i++) {
if (v[b[i]].size() == 0) {
flg = 1;
}
}
if (flg) {
cout << -1 << "\n";
continue;
}
int ans = 1, lst = 0;
for (int i = 1; i <= m; i++) {
if (upper_bound(v[b[i]].begin(), v[b[i]].end(), lst) == v[b[i]].end()) {
ans++;
lst = 0;
}
lst = v[b[i]][upper_bound(v[b[i]].begin(), v[b[i]].end(), lst) - v[b[i]].begin()];
}
cout << ans << "\n";
}
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1288kb
input:
10 sebgiuoczoemigefvlahqucwozknojbavqvroalawgbeyyxqro sduzprlgvftflmhvwxgzlizgvtikoudnhjulnacqwjcazr...
output:
-1 15 -1 -1 1 -1 -1 6 -1 1
result:
ok 10 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 1288kb
input:
10 qcyhppilxfzyhtxnhvvhdlaheytuppmeuonogsfumadymhmxrberabkedocjpuszituknqbgkhsiqaevo fkanwvqepspitbd...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 10 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 1284kb
input:
10 juphrputzg bkujvwsakuvwbshnbpcyukppchdhlwztffjngot ixlwahqcxtbnhjslellyrzfelfdtltpsvjmbimhuytxmcr...
output:
-1 4 -1 -1 -1 -1 18 -1 -1 -1
result:
ok 10 lines
Test #4:
score: 10
Accepted
time: 14ms
memory: 1696kb
input:
10 ttuqemikgpxkeymjlgseiojuqswwmznssmxyfnjaskakyxyexvsczxfqatmfhutjguengtfjuwunlgfxfkohwwghdfoqsplxe...
output:
26 37 36 32 60 50 36 7 12 7
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 18ms
memory: 1812kb
input:
10 zoszzoigfwwlfbkydwdcqloxdkskwhvojdjrqiwnrubsvykquywsrilgzqznzllkhzzjfwqlguvqumzbxgfmwfujsctbjjiks...
output:
22 6 29 38 48 12 25 34 27 32
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 15ms
memory: 1648kb
input:
10 tqooqroiawdbsqcnkrdpfgmuyzdsvufrrddkwjvjnnutilolejncyozrivccpmgkmxmsotxvrnjuosgtwjnvtmgygofvyywqm...
output:
149 13 67 16 16 11 33 39 15 30
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 13ms
memory: 1612kb
input:
10 liearkjhuusscmcwvvqkahoeaffwqaljknpzkigdlnllujcdtcnptzrijnxbbcgwcyojliircpyqkzstvmaggdjtfnqwoicml...
output:
19 13 35 5 31 13 31 27 11 19
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 14ms
memory: 1772kb
input:
10 kymwlbunfqaqmckjntfjgnrnvbekdsxtcpjvrepszyfbbeyxlyjhupiymdyyvrjexvuvmtskmmmmduzxkrosqenivlewnyyye...
output:
42 124 16 22 25 39 23 2 20 17
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 14ms
memory: 1840kb
input:
10 efzblaborigjcizqghvncfiuafstlfpqzdvjbafmizzijqzximreaqldfuhrrrwrrydpguhghgqewnmsniepiiaunnbbbbmyy...
output:
13 4 13 24 1 45 107 22 72 260
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 12ms
memory: 1800kb
input:
10 nlsfflwmguzcxupjoouzcerebughnqovfuwahtthulmiffgzcrlhnzqjutlaguhtydqfhetimspvnlzijtfvdsqeykpnnflku...
output:
280 15 38 11 215 28 107 66 5 3
result:
ok 10 lines
