Submission #646220

#	Time	Username	Problem	Language	Result	Execution time	Memory
646220		berr	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	3 ms	316 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
 
 
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    string s, t; cin>>s>>t;
    vector<int> kmp(400*5);
    int ss=0;

    int p=s.size();

    array<int,3> ans={0, 0, 0};
    s+=s;
  for(int i=8; i>=0; i--)
    {
        int tmp=ss+(1<<i);
        if(tmp<=p&&tmp<=t.size())
        {



            for(int l=0; l<=p-tmp; l++)
            {
                string k=s.substr(l, tmp);

                k+=k;

                k+=t;
                for(int j=0; j<tmp; j++)
                {
                    for(int l=i; l<k.size(); l++) kmp[l]=j;

                    for(int x=tmp*2; x<k.size(); x++)
                    {
                        int gh=kmp[x-1];
                        while(gh>j&&k[gh]!=k[x])
                        {
                            gh=k[gh-1];
                            break;
                        }

                        if(k[gh]==k[x])gh++;
                        kmp[x]=gh;


                            if(gh-j==tmp&&ans[0]!=tmp)
                            {

                                ans[0]=tmp;
                                ans[1]=l;

                                ans[2]=((x-tmp*3+1)%t.size()+t.size())%t.size();
                            }
                        
                    }
                }
            }

            if(ans[0]==tmp) ss=tmp;
        }
    }


    auto ans1=ans;
    ans={0, 0, 0};
    ss=0;


    reverse(s.begin(), s.end());
     for(int i=8; i>=0; i--)
    {
        int tmp=ss+(1<<i);
        if(tmp<=p&&tmp<=t.size())
        {

            for(int l=0; l<=p-tmp; l++)
            {
                string k=s.substr(l, tmp);

                k+=k;

                k+=t;
                for(int j=0; j<tmp; j++)
                {
                    for(int l=i; l<k.size(); l++) kmp[l]=j;

                    for(int x=tmp*2; x<k.size(); x++)
                    {
                        int gh=kmp[x-1];
                        while(gh>j&&k[gh]!=k[x])
                        {
                            gh=k[gh-1];
                            break;
                        }

                        if(k[gh]==k[x])gh++;
                        kmp[x]=gh;


                            if(gh-j==tmp&&ans[0]!=tmp)
                            {

                                ans[0]=tmp;
                                
                                ans[1]=((p-1)-(l+tmp-1));
                                
                                ans[2]=((x-tmp*3+1)%t.size()+t.size())%t.size();
                            }
                        
                    }
                }
            }

            if(ans[0]==tmp) ss=tmp;
        }
    }

    ans=max(ans1, ans);

    cout<<ans[0]<<"\n"<<ans[1]<<" "<<ans[2];
}

Compilation message (stderr)

necklace.cpp: In function 'int32_t main()':
necklace.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(tmp<=p&&tmp<=t.size())
      |                    ~~~^~~~~~~~~~
necklace.cpp:33:35: 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 l=i; l<k.size(); l++) kmp[l]=j;
      |                                  ~^~~~~~~~~
necklace.cpp:35:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |                     for(int x=tmp*2; x<k.size(); x++)
      |                                      ~^~~~~~~~~
necklace.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if(tmp<=p&&tmp<=t.size())
      |                    ~~~^~~~~~~~~~
necklace.cpp:87:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                     for(int l=i; l<k.size(); l++) kmp[l]=j;
      |                                  ~^~~~~~~~~
necklace.cpp:89:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                     for(int x=tmp*2; x<k.size(); x++)
      |                                      ~^~~~~~~~~

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