Submission #646282

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

necklace

#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;

    int p=s.size();
    s+=s;

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

        if(tmp<=p&&tmp<=t.size())
        {
            queue<int> q;
            map<int, int> mp;
            ans=0;
            for(int l=0; l<s.size()-1; 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)));
                    if(mp[ans]==0)
                    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=13; i>=0; i--)
    {
        int tmp=ss+(1<<i);

        if(tmp<=p&&tmp<=t.size())
        {
            queue<int> q;
            map<int, int> mp;
            ans=0;
            for(int l=0; l<s.size()-1; 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)));
                    if(mp[ans]==0)
                    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]=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];


}

Compilation message (stderr)

necklace.cpp: In function 'int32_t main()':
necklace.cpp:47:23: 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]
   47 |         if(tmp<=p&&tmp<=t.size())
      |                    ~~~^~~~~~~~~~
necklace.cpp:52: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]
   52 |             for(int l=0; l<s.size()-1; l++)
      |                          ~^~~~~~~~~~~
necklace.cpp:55: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]
   55 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:69: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]
   69 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:85: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]
   85 |             for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
      |                          ~^~~~~~~~~
necklace.cpp:87: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]
   87 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:101: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]
  101 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~
necklace.cpp:122:23: 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<=p&&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()-1; 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:160: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]
  160 |             for(int l=0; l<t.size()&&aa[0]!=tmp; l++)
      |                          ~^~~~~~~~~
necklace.cpp:162: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]
  162 |                 if(q.size()<tmp)
      |                    ~~~~~~~~^~~~
necklace.cpp:176: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]
  176 |                 if(q.size()==tmp)
      |                    ~~~~~~~~^~~~~

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