oj.uz

Submission #656173

# Submission time Handle Problem Language Result Execution time Memory
656173 2022-11-06T12:51:55 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 916 ms 141864 KB 
bool home = 0;
bool verbose = 1;

#include <bits/stdc++.h>

using namespace std;

int comps = 0;

void compute(vector<vector<int>>& dp, vector<vector<int>> &dp2, 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;
    }
  }
  dp2 = dp;
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      if (s[i] == t[j]) {
        dp[i][j] = 1;
        if (i + 1 < n && j + 1 < m) {
          dp[i][j] += dp[i + 1][j + 1];
        }
      } else {
        dp[i][j] = 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++;
      }
      dp2[last][first] = j;
      if (j == dim) {
        j = ps[j - 1];
      }
    }
  }
}

vector<vector<int>> longst;
vector<vector<int>> longts;
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];
    int max_possible_len = min(last + 1, (int) t.size() - first);
    for (int len = max_possible_len; len >= 1; len--) {
      if (longst[last - len + 1][first] >= len) {
        cout << " = " << len << " vs " << dpst[last][first] << "\n";
        return len;
      }
    }
    return 0;
  } else {
    if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) {
      return 0;
    }
    return dpts[last][first];
    int max_possible_len = min(last + 1, (int) s.size() - first);
    for (int len = max_possible_len; len >= 1; len--) {
      if (longts[last - len + 1][first] >= len) {
        return len;
      }
    }
    return 0;
  }
}

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();
    longst.clear();
    longts.clear();
    longst.resize(n, vector<int> (m));
    longts.resize(m, vector<int> (n));
    compute(longst, dpst, s, t);
    compute(longts, dpts, t, s);
    for (int last_a = 0; last_a < n; last_a++) {
      for (int first_a = 0; first_a < m; first_a++) {
        int first_b = last_a + 1;
        int last_b = first_a - 1;
        int cur = get_longest(last_a, first_a, 0) + get_longest(last_b, first_b, 1);
        if (cur > sol) {
          sol = cur;
          l = last_a;
          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();
  longst.clear();
  longts.clear();
  longst.resize(n, vector<int> (m));
  longts.resize(m, vector<int> (n));
  compute(longst, dpst, s, t);
  compute(longts, 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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 9 ms 2900 KB Output is correct
7 Correct 8 ms 2900 KB Output is correct
8 Correct 8 ms 2388 KB Output is correct
9 Correct 8 ms 2772 KB Output is correct
10 Correct 7 ms 2772 KB Output is correct
11 Correct 9 ms 2772 KB Output is correct
12 Correct 7 ms 2644 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 9 ms 2900 KB Output is correct
7 Correct 8 ms 2900 KB Output is correct
8 Correct 8 ms 2388 KB Output is correct
9 Correct 8 ms 2772 KB Output is correct
10 Correct 7 ms 2772 KB Output is correct
11 Correct 9 ms 2772 KB Output is correct
12 Correct 7 ms 2644 KB Output is correct
13 Correct 866 ms 141820 KB Output is correct
14 Correct 847 ms 141864 KB Output is correct
15 Correct 916 ms 133536 KB Output is correct
16 Correct 797 ms 139412 KB Output is correct
17 Correct 756 ms 136736 KB Output is correct
18 Correct 759 ms 140720 KB Output is correct
19 Correct 755 ms 140332 KB Output is correct
20 Correct 810 ms 136536 KB Output is correct
21 Correct 835 ms 138000 KB Output is correct