Submission #668682

#TimeUsernameProblemLanguageResultExecution timeMemory
668682gokussjzNecklace (Subtask 4) (BOI19_necklace4)C++17
15 / 15
299 ms468 KiB
#include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define all(x) x.begin(), x.end() #define pb push_back #define sz(x) (int)(x.size()) #define ll long long #define fi first #define se second #define lbd lower_bound #define ubd upper_bound template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int MOD = 1e9 + 7; const double eps = 1e-10; const long long INF = 1e18; const int N = 2e5 + 10; vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 1; i < n; i++) { int j = pi[i - 1]; while (j && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) j++; pi[i] = j; } return pi; } void solve() { string s, t; cin >> s >> t; int n = sz(s), m = sz(t); int ans = 0; pair<int, int> pos; for (int i = 0; i < n; i++) { string s1 = s.substr(0, i); string s2 = s.substr(i, n - i); reverse(all(s1)); string t1 = t; reverse(all(t1)); vector<int> p1 = prefix_function(s1 + '#' + t); vector<int> p2 = prefix_function(s2 + '#' + t1); for (int j = 1; j <= m; j++) { int curr = p1[i + j] + p2[n + m - i - j]; if (ans < curr) { ans = curr; pos = {i - p1[i + j], j - p1[i + j]}; } } } reverse(all(t)); for (int i = 0; i < n; i++) { string s1 = s.substr(0, i); string s2 = s.substr(i, n - i); reverse(all(s1)); string t1 = t; reverse(all(t1)); vector<int> p1 = prefix_function(s1 + '#' + t); vector<int> p2 = prefix_function(s2 + '#' + t1); for (int j = 1; j <= m; j++) { int curr = p1[i + j] + p2[n + m - i - j]; if (ans < curr) { ans = curr; pos = {i - p1[i + j], m - j - p2[n + m - i - j]}; } } } cout << ans << '\n' << pos.fi << ' ' << pos.se; } int main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solve(); cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...