oj.uz

Submission #955890

# Submission time Handle Problem Language Result Execution time Memory
955890 2024-03-31T16:14:35 Z simona1230 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 89 ms 139416 KB 
#include <bits/stdc++.h>

using namespace std;
const long long mult=31;
const long long mod=1e9+7;
string a,b;
long long p[3001];
long long h[3001][3001];
long long f[401][401][401];
map<long long,pair<long long,long long> > mp;

void prec()
{
    p[0]=1;
    for(long long i=1; i<=a.size(); i++)
        p[i]=(p[i-1]*mult)%mod;

    /*for(long long i=0; i<a.size(); i++)
    {
        h[i][i]=((a[i]-'a'+1)*mult)%mod;
        //cout<<a[i]<<" "<<h[i][i]<<endl;
        mp[h[i][i]]= {i+1,i+1};
        for(long long j=i+1; j<a.size(); j++)
        {
            h[i][j]=((h[i][j-1]+(a[j]-'a'+1))*mult)%mod;
            mp[h[i][j]]= {i+1,j+1};
        }
    }

    for(long long i=0; i<a.size(); i++)
    {
        for(long long j=i; j<a.size(); j++)
        {
            for(long long k=0; k<i; k++)
            {
                f[i][j][k]=(h[i][j]*p[i-k]+h[k][i-1])%mod;
                //cout<<f[i][j][k]<<endl;
                mp[f[i][j][k]]= {k+1,j+1};
            }
        }
    }*/

    reverse(a.begin(),a.end());
    for(long long i=0; i<a.size(); i++)
    {
        h[i][i]=((a[i]-'a'+1)*mult)%mod;
        //cout<<a[i]<<" "<<h[i][i]<<endl;
        mp[h[i][i]]= {a.size()-i,a.size()-i};
        for(long long j=i+1; j<a.size(); j++)
        {
            h[i][j]=((h[i][j-1]+(a[j]-'a'+1))*mult)%mod;
            mp[h[i][j]]= {a.size()-j,a.size()-i};
        }
    }

    for(long long i=0; i<a.size(); i++)
    {
        for(long long j=i; j<a.size(); j++)
        {
            for(long long k=0; k<i; k++)
            {
                f[i][j][k]=(h[i][j]*p[i-k]+h[k][i-1])%mod;
                //cout<<f[i][j][k]<<endl;
                mp[f[i][j][k]]= {a.size()-j,a.size()-k};
            }
        }
    }
}

void solve()
{
    long long len=0,l=0,r=0;
    for(long long i=0; i<b.size(); i++)
    {
        long long curr=0;
        for(long long j=i; j<b.size(); j++)
        {
            curr=((curr+(b[j]-'a'+1))*mult)%mod;
            //cout<<i<<" "<<j<<" "<<b[j]<<" "<<curr<<endl;
            if(mp[curr].first!=0&&(j-i+1)>=len)
            {
                len=j-i+1;
                l=mp[curr].first-1;
                r=i;
            }
        }
    }
    cout<<len<<endl;
    cout<<l<<" "<<r<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>a>>b;
    prec();
    solve();

    return 0;
}

Compilation message

necklace.cpp: In function 'void prec()':
necklace.cpp:15:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(long long i=1; i<=a.size(); i++)
      |                        ~^~~~~~~~~~
necklace.cpp:44:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(long long i=0; i<a.size(); i++)
      |                        ~^~~~~~~~~
necklace.cpp:49:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(long long j=i+1; j<a.size(); j++)
      |                              ~^~~~~~~~~
necklace.cpp:56:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(long long i=0; i<a.size(); i++)
      |                        ~^~~~~~~~~
necklace.cpp:58:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(long long j=i; j<a.size(); j++)
      |                            ~^~~~~~~~~
necklace.cpp: In function 'void solve()':
necklace.cpp:73:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(long long i=0; i<b.size(); i++)
      |                        ~^~~~~~~~~
necklace.cpp:76:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(long long j=i; j<b.size(); j++)
      |                            ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 136544 KB Output is correct
2 Correct 57 ms 136276 KB Output is correct
3 Correct 25 ms 104528 KB Output is correct
4 Correct 64 ms 137808 KB Output is correct
5 Incorrect 79 ms 139416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 136544 KB Output is correct
2 Correct 57 ms 136276 KB Output is correct
3 Correct 25 ms 104528 KB Output is correct
4 Correct 64 ms 137808 KB Output is correct
5 Incorrect 79 ms 139416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 136544 KB Output is correct
2 Correct 57 ms 136276 KB Output is correct
3 Correct 25 ms 104528 KB Output is correct
4 Correct 64 ms 137808 KB Output is correct
5 Incorrect 79 ms 139416 KB Output isn't correct
6 Halted 0 ms 0 KB -