제출 #646258

#제출 시각아이디문제언어결과실행 시간메모리
646258berrNecklace (Subtask 1-3) (BOI19_necklace1)C++17
29 / 85
1573 ms16712 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int h=37, mod=1e9+7;

int mul(int x, int y)
{
    return (x*y)%mod;
}

int sum(int x, int y)
{
    return((x+y)%mod+mod)%mod;
}

int poww(int a, int b)
{
    if(b==0) return 1;
    int tmp=poww(a, b/2);

    if(b%2==0) return mul(tmp, tmp);
    return mul(tmp, mul(tmp, a));
}

int inv(int a)
{
    return (poww(a, mod-2));
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    string s, t; cin>>s>>t;
  
    int ss=0;

    array<int, 3> aa={0, 0, 0};
    int ans=0;

    if(min(s.size(), t.size())<=100)
    {
    array<int, 3> aa={0, 0, 0};
     ans=0;

    for(int i=1; i<min(s.size(), t.size()); i++)
    {
        int tmp=i;

        if(tmp<=s.size()&&tmp<=t.size())
        {
            queue<int> q;
            map<int, int> mp;
            ans=0;
            for(int l=0; l<s.size(); l++)
            {

                if(q.size()<tmp)
                {
                   ans=sum(ans, mul((s[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }
                int pf=tmp;
                if(q.size()==tmp)
                while(pf--)
                {
                   q.front();
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.push(q.front());
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[q.front()]-'a'+1, poww(37, tmp)));
                    mp[ans]=l-tmp+2;
                    q.pop();
                }
            }

            q=queue<int>();
            ans=0;
            for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
            {
                if(q.size()<tmp)
                {
                   ans=sum(ans, mul((t[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(t[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(t[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }

                if(q.size()==tmp)
                {
                    if(mp.count(ans)>0) aa[0]=tmp, aa[1]=mp[ans]-1, aa[2]=l-tmp+1;
                }            
            }

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

    auto bb=aa;

    aa={0, 0, 0};
    ss=0, ans=0;
    reverse(s.begin(), s.end());


    for(int i=1; i<min(s.size(), t.size()); i++)
    {
        int tmp=i;
        if(tmp<=s.size()&&tmp<=t.size())
        {
            queue<int> q;
            map<int, int> mp;
            ans=0;
            for(int l=0; l<s.size(); l++)
            {

                if(q.size()<tmp)
                {
                   ans=sum(ans, mul((s[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }
                int pf=tmp;
                if(q.size()==tmp)
                while(pf--)
                {
                   q.front();
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.push(q.front());
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[q.front()]-'a'+1, poww(37, tmp)));
                    mp[ans]=l+1;
                    q.pop();
                }
            }

            q=queue<int>();
            ans=0;
            for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
            {
                if(q.size()<tmp)
                {
                   ans=sum(ans, mul((t[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(t[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(t[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }

                if(q.size()==tmp)
                {
                    if(mp.count(ans)>0) aa[0]=tmp, aa[1]=s.size()-mp[ans], aa[2]=l-tmp+1;
                }            
            }

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

    aa=max(aa, bb);
    cout<<aa[0]<<" \n"<<aa[1]<<" "<<aa[2];

}
else
{    for(int i=8; i>=0; i--)
    {
        int tmp=ss+(1<<i);

        if(tmp<=s.size()&&tmp<=t.size())
        {
            queue<int> q;
            map<int, int> mp;
            ans=0;
            for(int l=0; l<s.size(); l++)
            {

                if(l<tmp)
                {
                   ans=sum(ans, mul((s[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }
                int pf=tmp;
                if(q.size()==tmp)
                while(pf--)
                {
                   q.front();
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.push(q.front());
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[q.front()]-'a'+1, poww(37, tmp)));
                    mp[ans]=l-tmp+2;
                    q.pop();
                }
            }

            q=queue<int>();
            ans=0;
            for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
            {
                if(l<tmp)
                {
                   ans=sum(ans, mul((t[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(t[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(t[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }

                if(q.size()==tmp)
                {
                    if(mp.count(ans)>0) aa[0]=tmp, aa[1]=mp[ans]-1, aa[2]=l-tmp+1;
                }            
            }

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

    auto bb=aa;

    aa={0, 0, 0};
    ss=0, ans=0;
    reverse(s.begin(), s.end());


    for(int i=8; i>=0; i--)
    {
        int tmp=ss+(1<<i);

        if(tmp<=s.size()&&tmp<=t.size())
        {
            queue<int> q;
            map<int, int> mp;
            ans=0;
            for(int l=0; l<s.size(); l++)
            {

                if(q.size()<tmp)
                {
                   ans=sum(ans, mul((s[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }
                int pf=tmp;
                if(q.size()==tmp)
                while(pf--)
                {
                   q.front();
                    ans=sum(ans, mul(-1, mul(s[q.front()]-'a'+1, poww(37, 1))));
                    q.push(q.front());
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(s[q.front()]-'a'+1, poww(37, tmp)));
                    mp[ans]=l+1;
                    q.pop();
                }
            }

            q=queue<int>();
            ans=0;
            for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
            {
                if(q.size()<tmp)
                {
                   ans=sum(ans, mul((t[l]-'a'+1), poww(37, l+1)));
                   q.push(l);
                }
                else
                {
                    ans=sum(ans, mul(-1, mul(t[q.front()]-'a'+1, poww(37, 1))));
                    q.pop();
                    ans=mul(ans, inv(37));
                    ans=sum(ans, mul(t[l]-'a'+1, poww(37, tmp)));
                    q.push(l);
                }

                if(q.size()==tmp)
                {
                    if(mp.count(ans)>0) aa[0]=tmp, aa[1]=s.size()-mp[ans], aa[2]=l-tmp+1;
                }            
            }

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

    aa=max(aa, bb);
    cout<<aa[0]<<" \n"<<aa[1]<<" "<<aa[2];

}
}

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int32_t main()':
necklace.cpp:45:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
   45 |     for(int i=1; i<min(s.size(), t.size()); i++)
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:49:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(tmp<=s.size()&&tmp<=t.size())
      |            ~~~^~~~~~~~~~
necklace.cpp:49:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(tmp<=s.size()&&tmp<=t.size())
      |                           ~~~^~~~~~~~~~
necklace.cpp:54:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int l=0; l<s.size(); l++)
      |                          ~^~~~~~~~~
necklace.cpp:57:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   57 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:71:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   71 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:86:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
      |                          ~^~~~~~~~~
necklace.cpp:88:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:102:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  102 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:119:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
  119 |     for(int i=1; i<min(s.size(), t.size()); i++)
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:122:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         if(tmp<=s.size()&&tmp<=t.size())
      |            ~~~^~~~~~~~~~
necklace.cpp:122:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         if(tmp<=s.size()&&tmp<=t.size())
      |                           ~~~^~~~~~~~~~
necklace.cpp:127:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             for(int l=0; l<s.size(); l++)
      |                          ~^~~~~~~~~
necklace.cpp:130:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  130 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:144:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  144 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:159:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
      |                          ~^~~~~~~~~
necklace.cpp:161:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  161 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:175:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  175 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:194:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |         if(tmp<=s.size()&&tmp<=t.size())
      |            ~~~^~~~~~~~~~
necklace.cpp:194:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |         if(tmp<=s.size()&&tmp<=t.size())
      |                           ~~~^~~~~~~~~~
necklace.cpp:199:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             for(int l=0; l<s.size(); l++)
      |                          ~^~~~~~~~~
necklace.cpp:216:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  216 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:231:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |             for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
      |                          ~^~~~~~~~~
necklace.cpp:247:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  247 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:268:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  268 |         if(tmp<=s.size()&&tmp<=t.size())
      |            ~~~^~~~~~~~~~
necklace.cpp:268:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  268 |         if(tmp<=s.size()&&tmp<=t.size())
      |                           ~~~^~~~~~~~~~
necklace.cpp:273:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  273 |             for(int l=0; l<s.size(); l++)
      |                          ~^~~~~~~~~
necklace.cpp:276:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  276 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:290:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  290 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:305:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |             for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
      |                          ~^~~~~~~~~
necklace.cpp:307:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  307 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:321:28: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  321 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...