oj.uz

Submission #1085654

# Submission time Handle Problem Language Result Execution time Memory
1085654 2024-09-08T14:23:00 Z juicy Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 27 ms 20660 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using ull = unsigned long long;

const int N = 1e6 + 5, B = 331;

ull pw[N];

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

  pw[0] = 1;
  for (int i = 1; i < N; ++i) {
    pw[i] = pw[i - 1] * B;
  }  
  int t; cin >> t;
  while (t--) {
    string s; cin >> s;
    int n = s.size(), res = 0, l, r, len;
    ull a = 0, b = 0;
    for (l = 0, r = n - 1, len = 0; l < r; ++l, --r) {
      a = a * B + s[l] - 'a' + 1;
      b = (s[r] - 'a' + 1) * pw[len] + b;
      if (a == b) {
        a = b = len = 0;
        res += 2;
      } else {
        ++len;
      }
    }
    cout << res + (n & 1 || len) << "\n";
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8028 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8028 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8028 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 4 ms 8280 KB Output is correct
11 Correct 4 ms 8284 KB Output is correct
12 Correct 4 ms 8292 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8028 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 4 ms 8024 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 4 ms 8280 KB Output is correct
11 Correct 4 ms 8284 KB Output is correct
12 Correct 4 ms 8292 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 25 ms 20660 KB Output is correct
15 Correct 16 ms 15756 KB Output is correct
16 Correct 27 ms 19644 KB Output is correct
17 Correct 17 ms 14996 KB Output is correct