Submission #1097382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097382		simona1230	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	23 ms	2640 KiB

necklace

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;

string s1,s2;
void read()
{
    cin>>s1>>s2;
    s2+=s2;
}

int z[200001];

void solve()
{
    int ans=0,bg1=0,bg2=0;
    int n=s1.size();
    for(int i=0;i<s1.size();i++)
    {
        for(int j=i;j<s1.size();j++)
        {
            string s="";
            for(int k=i;k<=j;k++)
                s+=s1[k];
            
            cout<<s<<" "<<s2<<endl;
            s+=s2;
            int l=0,r=0;
            int maxx=0,idx=0;
            int m=s.size();
            for(int k=1;k<m;k++)
            {
                z[k]=0;
                if(i<r)
                {
                    z[k]=min(r-k,z[k-l]);
                }
                while(k+z[k]<m&&s[z[k]]==s[z[k]+1])
                    z[k]++;
                if(k+z[k]>r)
                {
                    r=k+z[k];
                    l=k;
                }
                
                if(k>=(j-i+1)&&z[k]+1>maxx&&s[0]==s[k])
                {
                    maxx=z[k]+1;
                    idx=k;
                }
            }
            
            maxx=min(maxx,(j-i+1));
            if(maxx>ans)
            {
                cout<<"in "<<maxx<<endl;
                ans=maxx;
                bg1=i;
                bg2=idx-(j-i+1);
            }
        }
    }
    cout<<ans<<endl<<bg1<<" "<<bg2<<endl;
}

int main() {
    read();
    solve();
    reverse(s1.begin(),s1.end());
    solve();
    
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void solve()':
necklace.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<s1.size();i++)
      |                 ~^~~~~~~~~~
necklace.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j=i;j<s1.size();j++)
      |                     ~^~~~~~~~~~
necklace.cpp:17:9: warning: unused variable 'n' [-Wunused-variable]
   17 |     int n=s1.size();
      |         ^

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