oj.uz

Submission #656161

# Submission time Handle Problem Language Result Execution time Memory
656161 2022-11-06T12:30:07 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 70988 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 (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;
      }
    }
  }
}

vector<vector<int>> longst;
vector<vector<int>> longts;
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;
    }
    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) {
        return len;
      }
    }
    return 0;
  } else {
    if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) {
      return 0;
    }
    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, s, t);
    compute(longts, t, s);

    /**

    AB
       BA
    **/
    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, s, t);
  compute(longts, 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:73:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:138:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |   if (rev == 0) {
      |   ^~
necklace.cpp:141:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     jump_b = (int) t.size() - (first_a + len_a);
      |                               ~~~~~~~~~^~~~~~~~
necklace.cpp:132:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |   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 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 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 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 24 ms 1500 KB Output is correct
7 Correct 39 ms 1504 KB Output is correct
8 Correct 47 ms 1372 KB Output is correct
9 Correct 70 ms 1564 KB Output is correct
10 Correct 66 ms 1492 KB Output is correct
11 Correct 66 ms 1492 KB Output is correct
12 Correct 55 ms 1500 KB Output is correct

Subtask #3
0.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 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 24 ms 1500 KB Output is correct
7 Correct 39 ms 1504 KB Output is correct
8 Correct 47 ms 1372 KB Output is correct
9 Correct 70 ms 1564 KB Output is correct
10 Correct 66 ms 1492 KB Output is correct
11 Correct 66 ms 1492 KB Output is correct
12 Correct 55 ms 1500 KB Output is correct
13 Execution timed out 1591 ms 70988 KB Time limit exceeded
14 Halted 0 ms 0 KB -