oj.uz

Submission #617113

# Submission time Handle Problem Language Result Execution time Memory
617113 2022-08-01T08:46:39 Z juancarlovieri Palinilap (COI16_palinilap) C++17
100 / 100
 80 ms 24888 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mod 1000000007

mt19937 gen(33);
uniform_int_distribution<> rd(1, 1000000000);
int pre[100005];
int prer[100005];
int pw[100005];
int p;
int all[100005][26];
int n;

int take(int l, int r) {
  int res = pre[r];
  if (l) {
    res -= pw[r - l + 1] * pre[l - 1] % mod;
  }
  res += mod;
  res %= mod;
  return res;
}

int takerev(int l, int r) {
  int res = prer[r];
  if (r) {
    res -= pw[r - l + 1] * prer[l - 1] % mod;
  }
  res += mod;
  res %= mod;
  return res;
}

bool eq(int a, int b, int c, int d) {
  return take(a, b) == takerev(n - d - 1, n - c - 1);
}

signed main() {
  p = rd(gen);
  string s;
  cin >> s;
  n = s.length();
  auto srev = s;
  reverse(srev.begin(), srev.end());
  pw[0] = 1;
  for (int i = 1; i < n; ++i) pw[i] = pw[i - 1] * p % mod;
  pre[0] = s[0] % mod;
  for (int i = 1; i < n; ++i) {
    pre[i] = (pre[i - 1] * p % mod + s[i]) % mod;
  }
  prer[0] = srev[0] % mod;
  for (int i = 1; i < n; ++i) {
    prer[i] = (prer[i - 1] * p % mod + srev[i]) % mod;
  }
  int act = 0;
  vector<pair<int, int>> diff(n + 5);
  // cout << pw[2] << endl;
  // cout << take(0, 1) <<  ' ' << take(2, 3) << endl;

  for (int i = 0; i < n; ++i) {
    for (int j = i; j <= i + 1; ++j) {
      if (j >= n) continue;
      int lo = 0, hi = min(i, n - j - 1);
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (eq(i - mid, i, j, j + mid)) {
        // if (take(i - mid, i) == take(j, j + mid)) {
          lo = mid + 1;
        } else hi = mid - 1;
      }
      if (hi >= 0) {
        // assert(take(i - hi, i) == take(j, j + hi)); 
      }
      // cout << "hi" << hi << ' ' << take(0, 1) << ' ' << takerev(0, 1) << endl;
      act += hi + 1;
      if (i == j) {
        diff[j + 1].first += -1;
        diff[j + hi + 1].first -= - 1;
        diff[j + 1].second += j + hi + 1;
        diff[j + hi + 1].second -= j + hi + 1;

        diff[i - (hi + 1) + 1].first += 1;
        diff[i].first -= 1;
        diff[i - (hi + 1) + 1].second += -(i - (hi + 1));
        diff[i].second -= -(i - (hi + 1));
      } else {
        diff[j].first += -1;
        diff[j + hi + 1].first -= - 1;
        diff[j].second += j + hi + 1;
        diff[j + hi + 1].second -= j + hi + 1;

        diff[i - (hi + 1) + 1].first += 1;
        diff[i + 1].first -= 1;
        diff[i - (hi + 1) + 1].second += -(i - (hi + 1));
        diff[i + 1].second -= -(i - (hi + 1));
      }

      int x = i - hi - 1;
      int y = j + hi + 1;
      if (x < 0 or y > n - 1) continue;
      lo = 1, hi = min(x, n - y - 1);
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (eq(x - mid, x - 1, y + 1, y + mid)) {
        // if (take(x - mid, x - 1) == take(y + 1, y + mid)) {
          lo = mid + 1;
        } else hi = mid - 1;
      }
      if (hi > 0) {
        // assert(take(x - hi, x - 1) == take(y + 1, y + hi));
      }
      // if (i == 0 and j == 1) cout << x << ' ' << y << ' ' << hi + 1 << endl;
      all[x][s[y] - 'a'] += hi + 1;
      all[y][s[x] - 'a'] += hi + 1;
    }
  }
  int ans = act;
  int cur = act;
  // cout << cur << endl;
  int delta = 0;
  int m = 0, c=  0;
  for (int i = 0; i < n; ++i) {
    // delta += diff[i];
    // cur += delta;
    m += diff[i].first;
    c += diff[i].second;
    // cout << delta << endl; 
    for (int j = 0; j < 26; ++j) {
      if ((s[i] - 'a') == j) continue;
      // cout << all[i][j] << ' ';
      // if (i == 1 and j == 2) cout << "INI " << all[i][j] << endl;
      ans = max(ans, cur + all[i][j] - (1ll * i * m + c));
      // if (i == 1 and j == 0) cout << cur << endl;
      // cout << i << ' ' << j << ' ' << cur + all[i][j] + 1 << endl;
    }
    // cout << endl;
    // cout << cur << ' ';
  }
  // cout << endl;
  cout << ans << endl;
  // delta += diff[n];
  // cur += delta;
  assert(cur == act);
  // cout << cur << endl;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:122:7: warning: unused variable 'delta' [-Wunused-variable]
  122 |   int delta = 0;
      |       ^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
37.0 / 37.0

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

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 24756 KB Output is correct
2 Correct 48 ms 24804 KB Output is correct
3 Correct 52 ms 24828 KB Output is correct
4 Correct 70 ms 24800 KB Output is correct
5 Correct 65 ms 24768 KB Output is correct
6 Correct 70 ms 24812 KB Output is correct
7 Correct 65 ms 24780 KB Output is correct
8 Correct 34 ms 4556 KB Output is correct
9 Correct 66 ms 24764 KB Output is correct
10 Correct 77 ms 24776 KB Output is correct
11 Correct 50 ms 24880 KB Output is correct
12 Correct 80 ms 24848 KB Output is correct
13 Correct 76 ms 24788 KB Output is correct
14 Correct 65 ms 24800 KB Output is correct
15 Correct 67 ms 24760 KB Output is correct
16 Correct 62 ms 24832 KB Output is correct
17 Correct 65 ms 24836 KB Output is correct
18 Correct 70 ms 24888 KB Output is correct
19 Correct 64 ms 24840 KB Output is correct