Submission #1098822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098822		simona1230	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	99 ms	2936 KiB

necklace

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
const int base=31;
const int mod=1e9+7;
string s1,s2;
long long h1[401][401];
long long h2[401][401];

void prec()
{
    for(int i=0;i<s1.size();i++)
    {
        h1[i][i]=(int)(s1[i]-'a'+1);
    }
    
    for(int l=2;l<=s1.size();l++)
    {
        for(int i=0;i+l<=s1.size();i++)
        {
            int j=i+l-1;
            h1[i][j]=(h1[i][j-1]*base+(int)(s1[j]-'a'+1))%mod;
        }
    }
    
    for(int i=0;i<s2.size();i++)
    {
        h2[i][i]=(int)(s2[i]-'a'+1);
    }
    
    for(int l=2;l<=s2.size();l++)
    {
        for(int i=0;i+l<=s2.size();i++)
        {
            int j=i+l-1;
            h2[i][j]=(h2[i][j-1]*base+(int)(s2[j]-'a'+1))%mod;
        }
    }
}

int ans;
int bg1,bg2;
int rev=0;
void solve()
{
    for(int i=0;i<s1.size();i++)
    {
        for(int j=0;j<s2.size();j++)
        {
            int ml1=0;
            for(int l1=1;l1<=s1.size();l1++)
            {
                int li=i-l1+1;
                int rj=j+l1-1;
                
                if(li<0||rj>=s2.size())break;
                if(h1[li][i]==h2[j][rj])ml1=l1;
            }
            
            int ml2=0;
            for(int l2=1;l2<=s2.size();l2++)
            {
                int ri=i+l2;
                int lj=j-l2;
                
                if(lj<0||ri>=s1.size())break;
                if(h1[i+1][ri]==h2[lj][j-1])ml2=l2;
            }
            
            ans=max(ans,ml1+ml2);
            if(ans==ml1+ml2)
            {
                bg1=i-ml1+1;
                if(rev)bg1=s1.size()-bg1-(ml1+ml2);
                bg2=j-ml2;
            }
        }
    }
}

int main() 
{
    cin>>s1>>s2;
    prec();
    solve();
    reverse(s1.begin(),s1.end());
    prec();
    rev=1;
    solve();
    cout<<ans<<endl;
    cout<<bg1<<" "<<bg2<<endl;
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void prec()':
necklace.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<s1.size();i++)
      |                 ~^~~~~~~~~~
necklace.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int l=2;l<=s1.size();l++)
      |                 ~^~~~~~~~~~~
necklace.cpp:19:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(int i=0;i+l<=s1.size();i++)
      |                     ~~~^~~~~~~~~~~
necklace.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<s2.size();i++)
      |                 ~^~~~~~~~~~
necklace.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int l=2;l<=s2.size();l++)
      |                 ~^~~~~~~~~~~
necklace.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i=0;i+l<=s2.size();i++)
      |                     ~~~^~~~~~~~~~~
necklace.cpp: In function 'void solve()':
necklace.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<s1.size();i++)
      |                 ~^~~~~~~~~~
necklace.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j=0;j<s2.size();j++)
      |                     ~^~~~~~~~~~
necklace.cpp:51:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int l1=1;l1<=s1.size();l1++)
      |                          ~~^~~~~~~~~~~
necklace.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 if(li<0||rj>=s2.size())break;
      |                          ~~^~~~~~~~~~~
necklace.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int l2=1;l2<=s2.size();l2++)
      |                          ~~^~~~~~~~~~~
necklace.cpp:66:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 if(lj<0||ri>=s1.size())break;
      |                          ~~^~~~~~~~~~~

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