oj.uz

Submission #403108

# Submission time Handle Problem Language Result Execution time Memory
403108 2021-05-12T18:43:56 Z rama_pang Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 432 KB 
#include <bits/stdc++.h>
using namespace std;

class HashString {
 public:
  const int KEY = 37;
  const int MOD = 1e9 + 9;

  int N;
  string S;
  vector<int> H;

  vector<int> power;
  vector<int> inv_power;

  HashString(string S) : S(S) {
    N = S.size();
    H.resize(N);
    power.resize(N);
    inv_power.resize(N);

    const auto Power = [&](int a, int x) {
      int z = 1;
      while (x) {
        if (x & 1) z = 1ll * z * a % MOD;
        x /= 2;
        a = 1ll * a * a % MOD;
      }
      return z;
    };

    power[0] = inv_power[0] = 1;
    power[1] = KEY;
    inv_power[1] = Power(KEY, MOD - 2);
    for (int i = 2; i < N; i++) {
      power[i] = 1ll * KEY * power[i - 1] % MOD;
      inv_power[i] = 1ll * inv_power[i - 1] * inv_power[1] % MOD;
    }

    for (int i = 0; i < N; i++) {
      assert(1ll * power[i] * inv_power[i] % MOD == 1);
    }

    for (int i = 0; i < N; i++) {
      H[i] = ((i > 0 ? H[i - 1] : 0) + 1ll * (S[i] - 'a' + 1) * power[i]) % MOD;
    }
  }

  int GetHash(int L, int R) {
    int res = (H[R] + MOD - (L > 0 ? H[L - 1] : 0)) % MOD;
    return 1ll * res * inv_power[L] % MOD;
  }
};

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

  string S, T;
  cin >> S >> T;

  const auto Solve = [&]() -> array<int, 3> {
    int N = S.size();
    int M = T.size();

    array<int, 3> ans = {0, 0, 0};
    HashString HS = HashString(S);
    HashString HT = HashString(T);

    // cout << HS.GetHash(2, 3) << ' ' << HT.GetHash(1, 2) << " hm\n";

    for (int t = 0; t < M; t++) {
      vector<int> dp(N);
      // dp[s] = longest suffix of T[0...t-1] which is a prefix of S[s...N]
      for (int s = 0; s < N; s++) {
        int lo = 0, hi = max(N, M);
        while (lo < hi) {
          int md = (lo + hi + 1) / 2;
          if (0 <= s - md + 1 && 0 <= t - md &&
              HS.GetHash(s - md + 1, s) == HT.GetHash(t - md, t - 1)) {
            lo = md;
          } else {
            hi = md - 1;
          }
        }
        // cout << s << ' ' << t << ' ' << lo << " getdp\n"; 
        dp[s - lo + 1] = max(dp[s - lo + 1], lo);
      }
      for (int s = 1; s < N; s++) {
        dp[s] = max(dp[s], dp[s - 1] - 1);
      }

      // cout << "DP: ";
      // for (int s = 0; s < N; s++) {
      //   cout << dp[s] << ' ';
      // }
      // cout << '\n';

      for (int s = 0; s < N; s++) {
        // Get longest common prefix starting with S[s...N], T[t...M]
        int lo = 0, hi = max(N, M);
        while (lo < hi) {
          int md = (lo + hi + 1) / 2;
          if (s + md - 1 < N && t + md - 1 < M &&
              HS.GetHash(s, s + md - 1) == HT.GetHash(t, t + md - 1)) {
            lo = md;
          } else {
            hi = md - 1;
          }
        }

        // S[s...s + lo - 1] == T[t...t + lo - 1]
        // Then, answer is lo + dp[s + lo]
        int len = lo + (s + lo == N ? 0 : dp[s + lo]);
        ans = max(ans, {len, s, t - dp[s + lo]});

        // cout << s << ' ' << t << ' ' << lo << ' ' << dp[s + lo] << " ha\n";
      }
    }

    return ans;
  };

  auto ans1 = Solve();
  reverse(begin(T), end(T));
  auto ans2 = Solve();
  ans2[2] = int(T.size()) - ans2[2] - ans2[0];
  auto ans = max(ans1, ans2);

  // auto ans = Solve();

  cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << '\n';
  return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 204 KB Output is correct
2 Correct 7 ms 204 KB Output is correct
3 Correct 6 ms 204 KB Output is correct
4 Correct 6 ms 204 KB Output is correct
5 Correct 6 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 204 KB Output is correct
2 Correct 7 ms 204 KB Output is correct
3 Correct 6 ms 204 KB Output is correct
4 Correct 6 ms 204 KB Output is correct
5 Correct 6 ms 204 KB Output is correct
6 Correct 136 ms 204 KB Output is correct
7 Correct 133 ms 236 KB Output is correct
8 Correct 114 ms 304 KB Output is correct
9 Correct 130 ms 308 KB Output is correct
10 Correct 130 ms 432 KB Output is correct
11 Correct 129 ms 204 KB Output is correct
12 Correct 124 ms 204 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 204 KB Output is correct
2 Correct 7 ms 204 KB Output is correct
3 Correct 6 ms 204 KB Output is correct
4 Correct 6 ms 204 KB Output is correct
5 Correct 6 ms 204 KB Output is correct
6 Correct 136 ms 204 KB Output is correct
7 Correct 133 ms 236 KB Output is correct
8 Correct 114 ms 304 KB Output is correct
9 Correct 130 ms 308 KB Output is correct
10 Correct 130 ms 432 KB Output is correct
11 Correct 129 ms 204 KB Output is correct
12 Correct 124 ms 204 KB Output is correct
13 Execution timed out 1591 ms 332 KB Time limit exceeded
14 Halted 0 ms 0 KB -