Submission #928830

#	Time	Username	Problem	Language	Result	Execution time	Memory
928830		Faisal_Saqib	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	25 / 85	1545 ms	19676 KiB

necklace

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define ll long long
ll powmod(ll a,ll b,ll c)
{
    if(b==1)
        return a;
    if(b==0)
        return 1;
    ll h=powmod(a,b/2,c);
    h=(h*h)%c;
    if(b&1)
        h=(h*a)%c;
    return h;
}
struct Hashing
{
    ll hash=0;
    deque<char> cp;
    ll l=0;
    ll base;
    ll mod;
    ll inv;
    Hashing(ll a=717,ll b=1e9+7){
        base=a;
        mod=b;
        inv=powmod(base,mod-2,mod);
    }
    void push_back(char& c)
    {
        hash=(((hash*base)%mod)+(c-'a'))%mod;
        cp.push_back(c);
        l++;
    }
    void push_front(char& c)
    {
        hash=(((powmod(base,l,mod)*(c-'a'))%mod)+hash)%mod;
        cp.push_front(c);
        l++;
    }
    void pop_back()
    {
        hash=(hash+mod-(cp.back()-'a'))%mod;
        hash=(hash*inv)%mod;
        cp.pop_back();
        l--;
    }
    char front()
    {
        return cp.front();
    }
    char back()
    {
        return cp.back();
    }
    int size()
    {
        return cp.size();
    }
    void pop_front()
    {
        l--;
        hash=(hash-((powmod(base,l,mod)*(cp.front()-'a'))%mod)+mod)%mod;
        cp.pop_front();
    }
    ll hash_value()
    {
        return hash;
    }
};
int main()
{
    string a,b;
    cin>>a>>b;
    map<pair<ll,ll>,int> fpp;
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        Hashing lp;
        Hashing lpp(919,1e9+9);
        Hashing lp1;
        Hashing lpp1(919,1e9+9);
        for(int j=i;j<n;j++)
        {
            lp.push_back(a[j]);
            lpp.push_back(a[j]);
            lp1.push_front(a[j]);
            lpp1.push_front(a[j]);
            for(int l=0;l<(j-i+1);l++)
            {
                fpp[{lp.hash_value(),lpp.hash_value()}]=i;
                fpp[{lp1.hash_value(),lpp1.hash_value()}]=i;
                char f=lp.front();
                lp.pop_front();
                lp.push_back(f);

                f=lpp.front();
                lpp.pop_front();
                lpp.push_back(f);

                f=lp1.front();
                lp1.pop_front();
                lp1.push_back(f);

                f=lpp1.front();
                lpp1.pop_front();
                lpp1.push_back(f);
            }
        }
    }
    int m=b.size();
    int mx=0;
    int ip=-1;
    int jp=-1;
    for(int i=0;i<m;i++)
    {
        Hashing tp;
        Hashing tpp(919,1e9+9);
        for(int j=i;j<m;j++)
        {
            tp.push_back(b[j]);
            tpp.push_back(b[j]);
            if(fpp.find({tp.hash_value(),tpp.hash_value()})!=fpp.end())
            {
                if((tp.size())>mx)
                {
                    mx=(int)(tp.size());
                    ip=fpp[{tp.hash_value(),tpp.hash_value()}];
                    jp=i;
                }
            }
        }
    }
    cout<<mx<<'\n';
    cout<<ip<<' '<<jp<<'\n';
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40