QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#261465	#7618. Pattern Search	xianggui^#	WA	1ms	5700kb	C++20	2.4kb	2023-11-22 21:59:35	2023-11-22 21:59:36

Judging History

你现在查看的是最新测评结果

[2023-11-22 21:59:36]
评测

测评结果：WA
用时：1ms
内存：5700kb

查看

[2023-11-22 21:59:35]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
char s[2000010],t[2000010];
ll num[30],tnum[30],snum[30];
int main()
{
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>s>>t;
        int ls=strlen(s);
        int lt=strlen(t);
        for(int i=0;i<26;i++) num[i]=tnum[i]=snum[i]=0;
        for(int i=0;i<ls;i++) snum[s[i]-'a']++;
        for(int i=0;i<lt;i++)
        {
            num[t[i]-'a']++;
        }
        ll minn=1e18;
        for(int i=0;i<26;i++)
        {
            if(!num[i]) continue;
            minn=min(minn, num[i]);
        }
        bool flag=0;
        for(int i=0;i<26;i++)
        {
            if(!num[i]) continue;
            if(num[i]!=1)
            {
                flag=1;
                break;
            }
        }
        if(!flag)
        {
            ll ans=1e18;
            for(int i=0;i<26;i++)
            {
                if(!num[i]) continue;
                ans=min(ans,snum[i]/num[i]);
            }
            cout<<ans<<'\n';
            continue;
        }
        flag=0;
        for(int i=0;i<26;i++)
        {
            if(!num[i]) continue;
            if(num[i]%minn)
            {
                flag=1;
                break;
            }
        }
        ll len=0;
        if(minn==1||flag)
        {
            ll ans=1e18;
            for(int i=0;i<26;i++)
            {
                if(!num[i]) continue;
                ll tem=num[i]/2;
                if(snum[i]<tem)
                {
                    ans=0;
                    break;
                }
                snum[i]-=tem;
                num[i]-=tem;
                ans=min(ans, snum[i]/num[i]);
            }
            cout<<ans<<'\n';
        }
        else
        {
            ll ans=1e18;
            for(int i=0;i<26;i++)
            {
                if(!num[i]) continue;
                ll tem=num[i]/minn*(minn-1);
                if(snum[i]<tem)
                {
                    ans=0;
                    break;
                }
                snum[i]-=tem;
                num[i]-=tem;
                ans=min(ans,snum[i]/num[i]);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}
/*
2
bajkaaall aal
abca cba

1
aaaabbbbcccc cbacbaba

*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5700kb

input:

2
bajkaaall aal
abca cba

output:

2
1

result:

ok 2 number(s): "2 1"

Test #2:

score: -100

Wrong Answer

time: 1ms

memory: 5612kb

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:

result:

wrong answer 10th numbers differ - expected: '2', found: '1'