oj.uz

Submission #841817

# Submission time Handle Problem Language Result Execution time Memory
841817 2023-09-02T06:55:49 Z WLZ Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 67 ms 12816 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = (int) 1e9 + 7;
const int p = 31;
 
/** Assumes 1 <= a, b < MOD */
int add(int a, int b) {
  if (a + b >= MOD) return a + b - MOD;
  return a + b;
}
 
/** Assumes 1 <= a, b < MOD */
int sub(int a, int b) {
  return add(a, MOD - b);
}
 
/** Assumes 1 <= a, b < MOD */
int mul(int a, int b) {
  return (long long) a * b % MOD;
}
 
/** Assumes 1 <= b < MOD */
int modpow(int b, int p) {
  if (p == 0) return 1;
  int ans = modpow(mul(b, b), p / 2);
  if (p % 2 == 1) ans = mul(ans, b);
  return ans;
}
 
int extgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int x1, y1, g = extgcd(b, a % b, x1, y1);
  x = y1; y = sub(x1, mul(y1, (a / b) % MOD));
  return g;
}
 
/** Assumes gcd(x, MOD) = 1 */ 
int inv(int x) {
  int x1, y1;
  extgcd(x, MOD, x1, y1);
  return x1;
}
 
void solve() {
  string s;
  cin >> s;
  int n = (int) s.length();
  int ans = 0;
  int l = 0, r = n - 1;
  while (l <= r) {
    bool found = false;
    int l_hash = 0, r_hash = 0, pw = 1;
    for (int i = l, j = r; i < j; i++, j--) {
      l_hash = add(mul(p, l_hash), s[i] - 'a' + 1);
      r_hash = add(r_hash, mul(pw, s[j] - 'a' + 1));
      pw = mul(pw, p);
      if (l_hash == r_hash && s.substr(l, i - l + 1) == s.substr(j, r - j + 1)) {
        found = true;
        l = i + 1; r = j - 1;
        break;
      }
    }
    if (!found) {
      ans++;
      break;
    }
    ans += 2;
  }
  cout << ans << '\n';
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 580 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 580 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 67 ms 12816 KB Output is correct
15 Correct 31 ms 7856 KB Output is correct
16 Correct 47 ms 11876 KB Output is correct
17 Correct 48 ms 7176 KB Output is correct