oj.uz

Submission #656177

# Submission time Handle Problem Language Result Execution time Memory
656177 2022-11-06T12:54:50 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 838 ms 71036 KB 
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; last_a++) {
      for (int first_a = 0; first_a < m; first_a++) {
        int cur = get_longest(last_a, first_a, 0) + get_longest(first_a - 1, last_a + 1, 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();
  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

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:133:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |   if (rev == 0) {
      |   ^~
necklace.cpp:136:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |     jump_b = (int) t.size() - (first_a + len_a);
      |                               ~~~~~~~~~^~~~~~~~
necklace.cpp:127:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |   int jump_a = last_a - len_a + 1;
      |                ~~~~~~~^~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 8 ms 1628 KB Output is correct
7 Correct 6 ms 1632 KB Output is correct
8 Correct 6 ms 1492 KB Output is correct
9 Correct 6 ms 1492 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 6 ms 1608 KB Output is correct
12 Correct 6 ms 1492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 8 ms 1628 KB Output is correct
7 Correct 6 ms 1632 KB Output is correct
8 Correct 6 ms 1492 KB Output is correct
9 Correct 6 ms 1492 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 6 ms 1608 KB Output is correct
12 Correct 6 ms 1492 KB Output is correct
13 Correct 838 ms 71036 KB Output is correct
14 Correct 762 ms 71032 KB Output is correct
15 Correct 747 ms 66892 KB Output is correct
16 Correct 733 ms 69936 KB Output is correct
17 Correct 677 ms 68556 KB Output is correct
18 Correct 650 ms 70556 KB Output is correct
19 Correct 681 ms 70340 KB Output is correct
20 Correct 715 ms 68428 KB Output is correct
21 Correct 695 ms 69324 KB Output is correct