제출 #646233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646233		berr	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	9 / 85	806 ms	468 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=0; 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=kmp[gh-1];
                        }

                        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=0; 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=kmp[gh-1];
                        }

                        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];
}

컴파일 시 표준 에러 (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:36:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                     for(int l=0; l<k.size(); l++) kmp[l]=j;
      |                                  ~^~~~~~~~~
necklace.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                     for(int x=tmp*2; x<k.size(); x++)
      |                                      ~^~~~~~~~~
necklace.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if(tmp<=p&&tmp<=t.size())
      |                    ~~~^~~~~~~~~~
necklace.cpp:88:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                     for(int l=0; l<k.size(); l++) kmp[l]=j;
      |                                  ~^~~~~~~~~
necklace.cpp:90:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                     for(int x=tmp*2; x<k.size(); x++)
      |                                      ~^~~~~~~~~

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