oj.uz

답안 #656156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656156 2022-11-06T12:27:29 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 1492 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;

int get_longest(int last, int first, string& s, string& t, bool cs) {
  string rev_t = t;
  reverse(rev_t.begin(), rev_t.end());
  int n = (int) s.size(), m = (int) t.size();
  if (!(0 <= last && last < n && 0 <= first && first < m)) {
    return 0;
  }
  int max_possible_len = min(last + 1, m - first);
  for (int len = max_possible_len; len >= 1; len--) {
    bool ok = 1;
    for (int i = 0; i < len; i++) {
      assert(0 <= first + i && first + i < (int) t.size());
      assert(0 <= last - len + 1 + i && last - len + 1 + i < (int) s.size());
      assert(t[first + i] == rev_t[(int) t.size() - 1 - first - i]);
      comps++;
      ok &= (s[last - len + 1 + i] == t[first + i]);
    }
    if (cs == 0) {
      assert(ok == (longst[last - len + 1][first] >= len));
    } else {
      assert(ok == (longts[last - len + 1][first] >= len));
    }
    if (ok) {
      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);
  }

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 400 KB Output is correct
2 Correct 53 ms 340 KB Output is correct
3 Correct 51 ms 372 KB Output is correct
4 Correct 59 ms 380 KB Output is correct
5 Correct 85 ms 376 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 400 KB Output is correct
2 Correct 53 ms 340 KB Output is correct
3 Correct 51 ms 372 KB Output is correct
4 Correct 59 ms 380 KB Output is correct
5 Correct 85 ms 376 KB Output is correct
6 Execution timed out 1592 ms 1492 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 400 KB Output is correct
2 Correct 53 ms 340 KB Output is correct
3 Correct 51 ms 372 KB Output is correct
4 Correct 59 ms 380 KB Output is correct
5 Correct 85 ms 376 KB Output is correct
6 Execution timed out 1592 ms 1492 KB Time limit exceeded
7 Halted 0 ms 0 KB -