oj.uz

답안 #651118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651118 2022-10-17T08:55:27 Z lto5 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 129 ms 36432 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3005;

short f[N][N], g[N][N];
int pi[N];
int ans;
int start_a = -1;
int start_b = -1;

void solve (string s, string t, bool reversed = false) {
  int n = s.size();
  int m = t.size();

  s = ' ' + s;
  t = ' ' + t;
  string cur = "";

  auto reset = [&]() {
    int lim = n + m + 5;
    for (int i = 0; i <= lim; i++)
      pi[i] = 0;
  };

  auto add = [&] (int i) -> int {
    int j = pi[i - 1];
    while (j > 0 && cur[j] != cur[i]) {
      j = pi[j - 1];
    }
    if (cur[i] == cur[j])
      pi[i] = j + 1;

    return pi[i];
  };

  for (int cut_b = 1; cut_b <= m; cut_b++) {
    reset();
    cur = t.substr(cut_b);
    cur = cur + '.';

    for (int i = 1; i < cur.size(); i++) {
      add(i);
    }

    for (int cut_a = 1; cut_a <= n; cut_a++) {
      cur.push_back(s[cut_a]);
      f[cut_a][cut_b] = add((int)cur.size() - 1);
    }
  }

  for (int cut_a = 1; cut_a <= n; cut_a++) {
    reset();
    cur = s.substr(cut_a);
    cur = cur + '.';

    for (int i = 1; i < cur.size(); i++) {
      add(i);
    }

    for (int cut_b = 1; cut_b <= m; cut_b++) {
      cur.push_back(t[cut_b]);
      g[cut_a][cut_b] = add((int)cur.size() - 1);
    }
  }

  for (int cut_a = 1; cut_a <= n; cut_a++)
    for (int cut_b = 1; cut_b <= m; cut_b++) {
      int cur = f[cut_a][cut_b] + g[cut_a + 1][cut_b - 1];
      if (ans < cur) {
        ans = cur;
        start_a = cut_a - f[cut_a][cut_b] + 1;
        start_b = cut_b - 1 - g[cut_a + 1][cut_b - 1] + 1;
        if (reversed) {
          start_b += cur - 1;
          start_b = m - start_b + 1;
        }
      }
    }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

//  freopen("input.txt", "r", stdin);

  string s, t;
  cin >> s >> t;

  solve(s, t);
  reverse(t.begin(), t.end());
  solve(s, t, 1);

  cout << ans << "\n";
  cout << start_a-1 << " " << start_b-1;

  return 0;
}

Compilation message

necklace.cpp: In function 'void solve(std::string, std::string, bool)':
necklace.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 1; i < cur.size(); i++) {
      |                     ~~^~~~~~~~~~~~
necklace.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 1; i < cur.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 10 ms 4176 KB Output is correct
7 Correct 9 ms 4216 KB Output is correct
8 Correct 9 ms 4044 KB Output is correct
9 Correct 12 ms 4052 KB Output is correct
10 Correct 7 ms 4104 KB Output is correct
11 Correct 9 ms 4180 KB Output is correct
12 Correct 9 ms 4052 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 10 ms 4176 KB Output is correct
7 Correct 9 ms 4216 KB Output is correct
8 Correct 9 ms 4044 KB Output is correct
9 Correct 12 ms 4052 KB Output is correct
10 Correct 7 ms 4104 KB Output is correct
11 Correct 9 ms 4180 KB Output is correct
12 Correct 9 ms 4052 KB Output is correct
13 Runtime error 129 ms 36432 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -