oj.uz

Submission #133362

# Submission time Handle Problem Language Result Execution time Memory
133362 2019-07-20T12:41:57 Z IOrtroiii Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 451 ms 508 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> eval(string s, string t) {
   int n = s.size();
   int m = t.size();
   vector<int> link(n);
   if (s.empty()) {
      return vector<int>(m, 0);
   }
   link[0] = -1;
   int cur = -1;
   for (int i = 1; i < n; ++i) {
      while (~cur && s[cur + 1] != s[i]) {
         cur = link[cur];
      }
      if (s[cur + 1] == s[i]) {
         cur++;
      }
      link[i] = cur;
   }
   cur = -1;
   vector<int> ans(m);
   for (int i = 0; i < m; ++i) {
      while (~cur && s[cur + 1] != t[i]) {
         cur = link[cur];
      }
      if (s[cur + 1] == t[i]) {
         cur++;
      }
      ans[i] = cur + 1;
   }
   return ans;
}

void debug(vector<int> a, string s) {
   cout << s << " ";
   for (int v : a) cout << v << " ";
   cout << "\n";
}

int main() {
   ios_base::sync_with_stdio(false);
   string s, t;
   cin >> s >> t;
   int n = s.size();
   int m = t.size();
   auto solve = [&]() {
      array<int, 3> ans = {0, 0, 0};
      for (int i = 0; i <= m; ++i) {
         string l, r;
         for (int j = 0; j < m; ++j) {
            if (j < i) {
               l += t[j];
            } else {
               r += t[j];
            }
         }
         reverse(l.begin(), l.end());
         reverse(s.begin(), s.end());
         auto gol = eval(l, s);
         reverse(gol.begin(), gol.end());
         reverse(s.begin(), s.end());
         auto gor = eval(r, s);
         // debug(gol, "gol is:");
         // debug(gor, "gor is:");
         for (int j = 0; j <= n; ++j) {
            int lenL = (j == 0 ? 0 : gor[j - 1]);
            int lenR = (j == n ? 0 : gol[j]);
            array<int, 3> cur = {lenL + lenR, j - lenL, i - lenR};
            ans = max(ans, cur);
         }
      }
      return ans;
   };
   auto l = solve();
   reverse(t.begin(), t.end());
   auto r = solve();
   cout << max(l[0], r[0]) << "\n";
   if (l[0] < r[0]) {
      cout << r[1] << " " << m - r[2] - r[0] << "\n";
   } else {
      cout << l[1] << " " << l[2] << "\n";
   }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 504 KB Output is correct
2 Correct 380 ms 508 KB Output is correct
3 Correct 451 ms 376 KB Output is correct
4 Correct 329 ms 504 KB Output is correct
5 Correct 318 ms 476 KB Output is correct
6 Correct 348 ms 376 KB Output is correct
7 Correct 367 ms 376 KB Output is correct
8 Correct 385 ms 376 KB Output is correct
9 Correct 399 ms 376 KB Output is correct