Submission #1174928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174928		InvMOD	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	0 / 85	1 ms	328 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(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(string a, string b){
    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;

//        cout << i << "\n";
//        cout << case_1 << "\n" << case_2 << "\n";

        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)];
            //cout << j <<" " << cur_value << " " << sz(x) + 1 + j <<" " << sz(pf2) - 1 - (j+1) << "\n";
            if(ckmx(answer, cur_value)){
                ps = i - pf1[sz(x) + 1 + j];
                pt = j - pf1[sz(x) + 1 + j] + 1;
            }
        }
    }
}

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

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

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

    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:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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