Submission #656182

#	Time	Username	Problem	Language	Result	Execution time	Memory
656182		600Mihnea	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	775 ms	71036 KiB

necklace

bool home = 0;
bool verbose = 1;

#include <bits/stdc++.h>

using namespace std;

int comps = 0;

void compute(vector<vector<int>>& dp,string &s, string &t) {
  int n = (int) s.size();
  int m = (int) t.size();
  assert((int) dp.size() == n);
  for (int i = 0; i < n; i++) {
    assert((int) dp[i].size() == m);
  }
  for (auto &v : dp) {
    for (auto &x : v) {
      x = 0;
    }
  }
  for (int first = 0; first < m; first++) {
    string guy(t.begin() + first, t.end());
    int dim = (int) guy.size();
    vector<int> ps(dim, 0);
    int j = 0;
    for (int i = 1; i < dim; i++) {
      while (j && guy[i] != guy[j]) {
        j = ps[j - 1];
      }
      if (guy[i] == guy[j]) {
        j++;
      }
      ps[i] = j;
    }
    j = 0;
    for (int last = 0; last < n; last++) {
      while (j && s[last] != guy[j]) {
        j = ps[j - 1];
      }
      if (s[last] == guy[j]) {
        j++;
      }
      dp[last][first] = j;
      if (j == dim) {
        j = ps[j - 1];
      }
    }
  }
}

vector<vector<int>> dpst;
vector<vector<int>> dpts;
string s;
string t;

int get_longest(int last, int first, bool cs) {
  if (cs == 0) {
    if (!(0 <= last && last < (int) s.size() && 0 <= first && first < (int) t.size())) {
      return 0;
    }
    return dpst[last][first];
  } else {
    if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) {
      return 0;
    }
    return dpts[last][first];
  }
}

int main() {

  if (!home) {
    verbose = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  }
  if (home) {
    verbose = 1;
    freopen ("___input___.txt", "r", stdin);
  }

  cin >> s >> t;

  int sol = -1, l, f, r;


  for (int rev_t = 0; rev_t <= 1; rev_t++) {
    int n = (int) s.size(), m = (int) t.size();
    dpst.resize(n, vector<int> (m));
    dpts.resize(m, vector<int> (n));
    compute(dpst, s, t);
    compute(dpts, t, s);
    for (int last_a = 0; last_a <= n - 2; last_a++) {
      {
        int cur =  dpst[last_a][0];
        if (cur > sol) {
          sol = cur;
          l = last_a;
          f = 0;
          r = rev_t;
        }
      }
      for (int first_a = 1; first_a < m; first_a++) {
        int cur = dpst[last_a][first_a] + dpts[first_a - 1][last_a + 1];
        if (cur > sol) {
          sol = cur;
          l = last_a;
          f = first_a;
          r = rev_t;
        }
      }
    }
    {
      for (int first_a = 0; first_a < m; first_a++) {
        int cur =  dpst[n - 1][first_a];
        if (cur > sol) {
          sol = cur;
          l = n - 1;
          f = first_a;
          r = rev_t;
        }
      }
    }
    reverse(t.begin(), t.end());
  }

  if (r) {
    reverse(t.begin(), t.end());
  }
  int n = (int) s.size(), m = (int) t.size();
  dpst.resize(n, vector<int> (m));
  dpts.resize(m, vector<int> (n));
  compute(dpst, s, t);
  compute(dpts, t, s);
  int rev = r;
  int last_a = l;
  int first_a = f;
  int first_b = last_a + 1;
  int last_b = first_a - 1;
  int len_a = get_longest(last_a, first_a, 0);
  int len_b = get_longest(last_b, first_b, 1);
  /// [last_a - len_a]
  /// [last_b - len_b]

  int jump_a = last_a - len_a + 1;
  int jump_b;

  /// [a, b]
  ///        [b, a]

  if (rev == 0) {
    jump_b = last_b - len_b + 1;
  } else {
    jump_b = (int) t.size() - (first_a + len_a);
  }
  if (verbose) {
    cout << "\t\t\t\t\tcomps = " << comps << "\n";
  }
  cout << sol << "\n";
  cout << jump_a << " " << jump_b << "\n";
  return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:81:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:153:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |   if (rev == 0) {
      |   ^~
necklace.cpp:156:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  156 |     jump_b = (int) t.size() - (first_a + len_a);
      |                               ~~~~~~~~~^~~~~~~~
necklace.cpp:147:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |   int jump_a = last_a - len_a + 1;
      |                ~~~~~~~^~~~~~~

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