QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224486 | #7618. Pattern Search | ucup-team1134# | RE | 0ms | 0kb | C++17 | 3.2kb | 2023-10-23 03:04:51 | 2023-10-23 03:04:53 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Q;cin>>Q;
while(Q--){
string S,T;cin>>S>>T;
vector<ll> cnS(26),cnT(26),neT(26),yoyuu(26);
for(char c:S) cnS[c-'a']++;
for(char c:T) cnT[c-'a']++;
bool f=true;
ll ans=INF;
for(int i=0;i<26;i++){
if(cnS[i]<cnT[i]) f=false;
chmin(ans,cnS[i]/cnT[i]-1);
cnS[i]-=cnT[i];
}
if(!f){
cout<<0<<"\n";
continue;
}
vector<ll> check(si(T));iota(all(check),1);
shuffle(all(check),rng);
for(ll k:check){
ll need=(si(T)+k-1)/k,giri=si(T)/k;
ll sum=0;
bool f=true;
for(int i=0;i<26;i++){
sum+=(cnT[i]+need-1)/need*need;
neT[i]=(cnT[i]+need-1)/need;
yoyuu[i]=cnT[i]/giri-neT[i];
if(neT[i]*giri>cnT[i]) f=false;
}
if(!f) continue;
ll X=(need*k-sum)/need;
if(X<0) continue;
if(X==0){
ll mi=1LL<<60;
for(int i=0;i<26;i++){
if(cnT[i]) chmin(mi,cnS[i]/neT[i]);
}
chmax(ans,mi);
continue;
}
if(ans){
ll can=0;
for(int i=0;i<26;i++){
if(yoyuu[i]>0){
can+=min(yoyuu[i],max(0LL,cnS[i]/ans-neT[i]));
if(cnS[i]/ans-neT[i]<0){
can=-1;
break;
}
}
}
if(can<X) continue;
}
ll left=ans,right=1LL<<28;
while(right-left>1){
ll mid=(left+right)/2;
ll can=0;
for(int i=0;i<26;i++){
if(yoyuu[i]>0){
can+=min(yoyuu[i],max(0LL,cnS[i]/mid-neT[i]));
if(cnS[i]/mid-neT[i]<0){
can=-1;
break;
}
}
}
if(can>=X) left=mid;
else right=mid;
}
chmax(ans,left);
}
cout<<ans+1<<"\n";
}
}
详细
Test #1:
score: 0
Runtime Error
input:
2 bajkaaall aal abca cba