oj.uz

Submission #1098822

# Submission time Handle Problem Language Result Execution time Memory
1098822 2024-10-10T06:02:14 Z simona1230 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 99 ms 2936 KB 
// 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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 956 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 956 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 94 ms 2936 KB Output is correct
7 Correct 99 ms 2904 KB Output is correct
8 Correct 71 ms 2652 KB Output is correct
9 Correct 89 ms 2648 KB Output is correct
10 Correct 91 ms 2904 KB Output is correct
11 Correct 89 ms 2904 KB Output is correct
12 Correct 82 ms 2652 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 956 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 94 ms 2936 KB Output is correct
7 Correct 99 ms 2904 KB Output is correct
8 Correct 71 ms 2652 KB Output is correct
9 Correct 89 ms 2648 KB Output is correct
10 Correct 91 ms 2904 KB Output is correct
11 Correct 89 ms 2904 KB Output is correct
12 Correct 82 ms 2652 KB Output is correct
13 Runtime error 3 ms 2908 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -