QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311329 | #7618. Pattern Search | PlentyOfPenalty# | RE | 0ms | 5584kb | C++20 | 2.0kb | 2024-01-22 10:47:12 | 2024-01-22 10:47:13 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int N = 2e6;
int T, n, m, ts[30], tt[30], TIM1, TIM2;
int l, r, mid;
int mx, nm, an[N + 10], vis1[N + 10], vis2[N + 20];
string s, t;
void Ins(int x) {
if (vis1[x] != TIM1) vis1[x] = TIM1, an[x] = 0;
if (vis2[x] == TIM2) return;
vis2[x] = TIM2;
if ((++an[x]) > mx) mx = an[x];
}
bool Check(int x) {
// cout << "CHECK " << x << "\n";
int lm, tl, tr, tmp;
++TIM1;
mx = nm = 0;
for (int i = 0; i < 26 && nm == mx; ++i)
if (tt[i]) {
// cout << "i=" << i << "\n";
++nm;
lm = ts[i] / x;
// cout << "LM=" << lm << "\n";
tl = 1;
++TIM2;
while (tl <= lm) {
tr = tt[i] / (tmp = tt[i] / tl);
if (tt[i] % tr == 0)
Ins(tmp - 1), Ins(tmp);
else
Ins(tmp - 1);
tl = tr + 1;
}
}
return nm == mx;
}
int main() {
#ifdef popteam
freopen("M.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> T;
while (T--) {
cin >> s >> t;
n = s.size(), m = t.size();
for (int i = 0; i < 26; ++i)
ts[i] = tt[i] = 0;
for (int i = 0; i < n; ++i)
++ts[s[i] - 'a'];
for (int i = 0; i < m; ++i)
++tt[t[i] - 'a'];
l = 0, r = n;
for (int i = 0; i < 26; ++i) {
if (ts[i] < tt[i]) {
cout << "0\n";
goto Skip;
}
if (!tt[i]) continue;
ts[i] -= tt[i];
// cout << "TS " << i << "=" << ts[i] << "\n";
}
// cout << "DONE.l=" << l << " r=" << r << "\n";
while (l < r) {
mid = (l + r + 1 >> 1);
if (Check(mid))
l = mid;
else
r = mid - 1;
}
cout << l + 1 << "\n";
Skip:;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5584kb
input:
2 bajkaaall aal abca cba
output:
2 1
result:
ok 2 number(s): "2 1"
Test #2:
score: -100
Runtime Error
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