Submission #1095103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1095103	2024-10-01T09:33:42 Z	BF001	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	271 ms	600 KB

necklace

#include<bits/stdc++.h>
using namespace std;
 
#define N 6005
#define fi first
#define se second

typedef pair<int, pair<int, int>> ii;

int n, m, pi1[N], pi2[N];
ii res = {0, {0, 0}};
string s, t;
 
ii solve(string s, string t, int ne){
    ii rt = {0, {0, 0}};
    int si = (int) s.size() - 1;
    for (int i = 0; i < (int) s.size(); i++){
        string s1 = "", s2 = "",t2 = t;
        for (int j = 0; j <= i; j++) s1 += s[j];
        for (int j = i + 1; j < (int) s.size(); j++) s2 += s[j];
        s2 = s2 + "#" + t;
        reverse(t2.begin(), t2.end());
        reverse(s1.begin(), s1.end());
        s1 = s1 + "#" + t2;
        for (int j = 1; j < (int) s1.size(); j++){
            int pos = pi1[j - 1];
            while (pos > 0 && s1[pos] != s1[j]) pos = pi1[pos - 1];
            if (s1[pos] == s1[j]) pos++;
            pi1[j] = pos;
        }
        for (int j = 1; j < (int) s2.size(); j++){
            int pos = pi2[j - 1];
            while (pos > 0 && s2[pos] != s2[j]) pos = pi2[pos - 1];
            if (s2[pos] == s2[j]) pos++;
            pi2[j] = pos;
        }
        int n = (int) s1.size();
        int m = (int) s2.size();
        for (int j = 0; j < (int) t.size(); j++){
            int suf = pi2[j + 1 + si - i];
            int pre = 0;
            if (j != (int) t.size() - 1) pre = pi1[i + 1 + (int) t.size()  - (j + 1)];
            if (pre + suf > rt.fi)
            rt =  {pre + suf, {i - pre + 1, j - suf + 1}};
        }
    }
    if (ne) {
        rt.se.se = (int) t.size() - 1 - rt.se.se - rt.fi + 1;
    }
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> s;
    cin >> t;

    res = solve(s, t, 0);
    reverse(t.begin(), t.end());
    res = max(res, solve(s, t, 1));

    cout << res.fi << "\n";
    cout << res.se.fi << " " << res.se.se;
 
    return 0;
}

Compilation message

necklace.cpp: In function 'ii solve(std::string, std::string, int)':
necklace.cpp:37:13: warning: unused variable 'n' [-Wunused-variable]
   37 |         int n = (int) s1.size();
      |             ^
necklace.cpp:38:13: warning: unused variable 'm' [-Wunused-variable]
   38 |         int m = (int) s2.size();
      |             ^

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	258 ms	572 KB	Output is correct
2	Correct	214 ms	552 KB	Output is correct
3	Correct	271 ms	552 KB	Output is correct
4	Correct	200 ms	560 KB	Output is correct
5	Correct	204 ms	348 KB	Output is correct
6	Correct	222 ms	596 KB	Output is correct
7	Correct	217 ms	600 KB	Output is correct
8	Correct	230 ms	556 KB	Output is correct
9	Correct	234 ms	344 KB	Output is correct