Submission #687517

#	Time	Username	Problem	Language	Result	Execution time	Memory
687517		Kripton	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	375 ms	364 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

int pi[6005];
int kmp1[3005], kmp2[3005];

pair <int, int> solve(string a, string b)//size(a) < size(b)
{
    pair <int, int> max1 = {0, 0};
    for(int i = 0; i < b.size(); i++)
    {
        ///rezolv
        string s = "#" + b + "*" + a;
        pi[1] = 0;
        for(int j = 2; j < s.size(); j++)
        {
            pi[j] = pi[j - 1];
            while(pi[j] && s[pi[j] + 1] != s[j])
                pi[j] = pi[pi[j]];
            if(s[pi[j] + 1] == s[j])
                pi[j]++;
        }
        for(int j = 1; j <= a.size(); j++)
            kmp1[j] = pi[j + 1 + b.size()];
        string ca, cb;
        ca = a;
        cb = b;
        reverse(ca.begin(), ca.end());
        reverse(cb.begin(), cb.end());
        s = "#" + cb + "*" + ca;
        pi[1] = 0;
        for(int j = 2; j < s.size(); j++)
        {
            pi[j] = pi[j - 1];
            while(pi[j] && s[pi[j] + 1] != s[j])
                pi[j] = pi[pi[j]];
            if(s[pi[j] + 1] == s[j])
                pi[j]++;
        }
        for(int j = 1; j <= a.size(); j++)
            kmp2[a.size() - j + 1] = pi[j + 1 + b.size()];
        /*cout << a << '\n' << b << '\n';
        for(int j = 1; j <= a.size(); j++)
            cout << kmp1[j] << " ";
        cout << '\n';
        for(int j = 1; j <= a.size(); j++)
            cout << kmp2[j] << " ";
        cout << '\n';*/
        for(int j = 1; j < a.size(); j++)
            if(kmp1[j] + kmp2[j + 1] > max1.first)
            {
                max1.first = kmp1[j] + kmp2[j + 1];
                //cout << kmp1[j] + kmp2[j + 1] << " " << j <<'\n';
                max1.second = (j - kmp1[j]) * 10000 + (b.size() - kmp2[j + 1] - i + b.size()) % b.size();
            }
        rotate(b.begin(), prev(b.end()), b.end());
    }
    return max1;
}

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
    string a, b;
    bool ok;
    cin >> a >> b;
    if(a.size() > b.size())
    {
        ok = 1;
        swap(a, b);
    }
    string cb = b;
    b += '$';
    pair <int, int> ans1 = solve(a, b);
    reverse(cb.begin(), cb.end());
    cb += '$';
    pair <int, int> ans2 = solve(a, cb);
    if(ans1.first > ans2.first)
    {
        cout << ans1.first << '\n';
        if(ok == 0)
            cout << ans1.second / 10000 << " " << ans1.second % 10000;
        else
            cout << ans1.second % 10000 << " " << ans1.second / 10000;
    }
    else
    {
        cout << ans2.first << '\n';
        if(ok == 0)
            cout << ans2.second / 10000 << " " << (b.size() - 1 - ans2.second % 10000 - ans2.first + 1 + b.size()) % b.size();
        else
            cout << (b.size() - 1 - ans2.second % 10000 - ans2.first + 1 + b.size()) % b.size() << " " << ans2.second / 10000;
    }
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'std::pair<int, int> solve(std::string, std::string)':
necklace.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0; i < b.size(); i++)
      |                    ~~^~~~~~~~~~
necklace.cpp:15:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(int j = 2; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int j = 1; j <= a.size(); j++)
      |                        ~~^~~~~~~~~~~
necklace.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j = 2; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 1; j <= a.size(); j++)
      |                        ~~^~~~~~~~~~~
necklace.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j = 1; j < a.size(); j++)
      |                        ~~^~~~~~~~~~

• Subtask 1: 0 / 15