oj.uz

Submission #928825

# Submission time Handle Problem Language Result Execution time Memory
928825 2024-02-17T06:23:30 Z Faisal_Saqib Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 19652 KB 
#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((int)(tp.size())>mx)
                {
                    mx=(int)(tp.size());
                    ip=fpp[{tp.hash_value(),tpp.hash_value()}];
                    jp=i;
                }
            }
        }
    }
    cout<<mx<<endl;
    cout<<ip<<' '<<jp<<endl;
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9860 KB Output is correct
2 Correct 105 ms 8712 KB Output is correct
3 Correct 44 ms 3172 KB Output is correct
4 Correct 127 ms 12360 KB Output is correct
5 Correct 202 ms 19540 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9860 KB Output is correct
2 Correct 105 ms 8712 KB Output is correct
3 Correct 44 ms 3172 KB Output is correct
4 Correct 127 ms 12360 KB Output is correct
5 Correct 202 ms 19540 KB Output is correct
6 Execution timed out 1547 ms 19652 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9860 KB Output is correct
2 Correct 105 ms 8712 KB Output is correct
3 Correct 44 ms 3172 KB Output is correct
4 Correct 127 ms 12360 KB Output is correct
5 Correct 202 ms 19540 KB Output is correct
6 Execution timed out 1547 ms 19652 KB Time limit exceeded
7 Halted 0 ms 0 KB -