QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #227293 | #7618. Pattern Search | ftt2333 | WA | 0ms | 3724kb | C++14 | 909b | 2023-10-27 10:36:50 | 2023-10-27 10:36:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int maxn = 1e6 + 10, inf = 1e9;
char s[maxn], t[maxn];
int a[26], b[26], n, m;
void solve() {
for (int i = 0; i < 26; ++i) a[i] = b[i] = 0;
scanf("%s%s", s + 1, t + 1);
n = strlen(s + 1), m = strlen(t + 1);
for (int i = 1; i <= n; ++i) ++a[s[i] - 'a'];
for (int i = 1; i <= m; ++i) ++b[t[i] - 'a'];
for (int i = 0; i < 26; ++i) a[i] -= b[i];
for (int i = 0; i < 26; ++i) {
if (a[i] < 0) return cout << 0 << '\n', void();
}
int ans1 = inf, ans2 = inf;
int g = 0;
for (int i = 0; i < 26; ++i) g = __gcd(g, b[i]);
for (int i = 0; i < 26; ++i) if (b[i]) ans1 = min(ans1, a[i] / (b[i] / g));
for (int i = 0; i < 26; ++i) if (b[i]) ans2 = min(ans2, a[i] / (b[i] + 1 >> 1));
cout << max(ans1, ans2) + 1 << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
2 bajkaaall aal abca cba
output:
2 1
result:
ok 2 number(s): "2 1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3684kb
input:
16 a a a b b a aa a ab aa ab b ab c aaz az abcde edcba aaaaaaaaaaaabbb aaaaaaaaabb aaaaaazz az aaaaaaaaaz zzzzz gggggggggggggggggggge ggggeeee hyphyphyphyphyphyphyphyphyphyphyphyp eeeeeeeeee hyphyphyphyphyphyphyphyphyphyphyphype eeteeteeteet aaaabbbbbbcccccccc aaabbbbbcccccc
output:
1 0 0 2 0 1 0 1 1 1 2 0 0 0 0 1
result:
wrong answer 10th numbers differ - expected: '2', found: '1'