Submission #1174947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174947		InvMOD	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	222 ms	612 KiB

necklace

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()

template<typename T> bool ckmx(T& a, const T& b){
    if(a < b)
        return a = b, true;
    return false;
}

vector<int> calc_kmp(const string &s){
    vector<int> pf(sz(s), 0);
    for(int i = 1; i < sz(s); i++){
        int j = pf[i - 1];
        while(j > 0 && s[j] != s[i]) j = pf[j - 1];
        pf[i] = (s[j] == s[i] ? j + 1 : 0);
    }
    return pf;
}

int answer, ps, pt;

void find_optimal(const string &a, const string &b, bool rev){
    string rev_b = b; reverse(all(rev_b));
    for(int i = 0; i <= sz(a); i++){

        string x = a.substr(0, i), y = a.substr(i);
        string rev_x = x; reverse(all(rev_x));

        string case_1 = rev_x + "#" + b;
        string case_2 = y + "#" + rev_b;

        vector<int> pf1 = calc_kmp(case_1);
        vector<int> pf2 = calc_kmp(case_2);

        for(int j = 0; j < sz(b); j++){
            // cut at each j
            int cur_value = pf1[sz(x) + 1 + j] + pf2[sz(pf2) - 1 - (j+1)];
            if(ckmx(answer, cur_value)){
                ps = i - pf1[sz(x) + 1 + j];
                pt = (!rev ? j - pf1[sz(x) + 1 + j] + 1 : (sz(b) - 1) - (j + pf2[sz(pf2) - 1 - (j + 1)]));
                // remember there is [r, l] so if we swap we have to swap r,l too :<
            }
        }
    }
}

void solve()
{
    string s,t; cin >> s >> t;

    answer = -1, ps = -1, pt = -1;
    find_optimal(s, t, false);

    reverse(all(t));
    find_optimal(s, t, true);

    cout << answer << "\n";
    cout << ps <<" " << pt << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int32_t main()':
necklace.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15