QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #404764 | #7618. Pattern Search | ucup-team3215# | WA | 0ms | 3588kb | C++20 | 700b | 2024-05-04 17:37:08 | 2024-05-04 17:37:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (int tc = (cin >> tc, tc); tc--; ) {
int ct[26]{}, cp[26]{};
string t, p; cin >> t >> p;
for (auto c: t) ++ct[c - 'a'];
for (auto c: p) ++cp[c - 'a'];
int l = 0, r = t.size();
while (r > l + 1) {
int m = (l + r) / 2;
bool ok = 0;
for (int n = 1; !ok && n <= p.size(); ++n) {
ok = 1;
for (int i = 0; ok && i < 26; ++i) if (cp[i]) {
int a = (cp[i] + n) / (n + 1), b = cp[i] - a * n;
ok &= ct[i] >= (m + n - 1ll) * a + b;
}
}
(ok? l: r) = m;
}
cout << l << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
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: 3548kb
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:
0 0 0 1 0 1 0 1 1 2 2 0 0 0 0 2
result:
wrong answer 1st numbers differ - expected: '1', found: '0'