Submission #140737

#	Time	Username	Problem	Language	Result	Execution time	Memory
140737		Minnakhmetov	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	366 ms	632 KiB

necklace

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 6005;
string a, b;
int p1[N], p2[N];

void prefixFunction(string a, const string &b, int p[N]) {
    a = a + "#" + b;

    p[0] = 0;

    for (int i = 1; i < a.size(); i++) {
        int x = p[i - 1];
        while (x > 0 && a[x] != a[i])
            x = p[x - 1];
        if (a[x] == a[i])
            x++;
        p[i] = x;
    }

    for (int i = 0; i < b.size(); i++)
        p[i] = p[a.size() - b.size() + i];
}

tuple<int, int, int> calc(string a, string b, bool rev) {
    b += '$';

    int ans = -1, x, y;

    for (int i = 0; i < b.size() - 1; i++) {
        prefixFunction(b, a, p1);
        reverse(all(b));
        reverse(all(a));
        prefixFunction(b, a, p2);
        reverse(p2, p2 + a.size());
        reverse(all(b));
        reverse(all(a));        

        for (int j = -1; j < (int)a.size(); j++) {
            int cur = 0;

            if (j >= 0)
                cur += p1[j];
            if (j + 1 < a.size())
                cur += p2[j + 1];

            if (cur > ans) {
                ans = cur;
                x = (j < 0 ? 0 : j - p1[j] + 1);
                y = i - (j + 1 < a.size() ? p2[j + 1] : 0);
            }
        }

        for (int j = 0; j < b.size() - 1; j++)
            swap(b[j], b[j + 1]);
    }

    if (rev)
        y = b.size() - 1 - y - ans;

    return { ans, x, y };
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b;

    auto ans = calc(a, b, false);
    reverse(all(b));
    ans = max(ans, calc(a, b, true));

    cout << get<0>(ans) << "\n" << get<1>(ans) << " " << get<2>(ans);

    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void prefixFunction(std::__cxx11::string, const string&, int*)':
necklace.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); i++) {
                     ~~^~~~~~~~~~
necklace.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size(); i++)
                     ~~^~~~~~~~~~
necklace.cpp: In function 'std::tuple<int, int, int> calc(std::__cxx11::string, std::__cxx11::string, bool)':
necklace.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size() - 1; i++) {
                     ~~^~~~~~~~~~~~~~
necklace.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j + 1 < a.size())
                 ~~~~~~^~~~~~~~~~
necklace.cpp:54:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 y = i - (j + 1 < a.size() ? p2[j + 1] : 0);
                          ~~~~~~^~~~~~~~~~
necklace.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < b.size() - 1; j++)
                         ~~^~~~~~~~~~~~~~
necklace.cpp:63:26: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
         y = b.size() - 1 - y - ans;
             ~~~~~~~~~~~~~^~~

• Subtask 1: 15 / 15