oj.uz

Submission #977810

# Submission time Handle Problem Language Result Execution time Memory
977810 2024-05-08T11:18:45 Z duckindog Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 39 ms 26440 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int t;

using ull = unsigned long long;
ull h[N], pw[N];
ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  pw[0] = 1;
  for (int i = 1; i <= 1'000'000; ++i) pw[i] = pw[i - 1] * 19937;

  cin >> t;
  while (t--) { 
    string s; cin >> s;
    for (int i = 1; i <= s.size(); ++i) h[i] = h[i - 1] * 19937 + s[i - 1];
    
    int l = 1, r = s.size();
    int answer = 0;
    
    int len = 0;
    while (l <= r) {
      if (l + len >= r - len) { answer += 1; break; }
      
      if (get(l, l + len) != get(r - len, r)) len += 1;
      else { 
        answer += 2;
        l = l + len + 1; r = r - len - 1;
        len = 0;
      }
    }

    cout << answer << "\n";
  }
}

Compilation message

palindromic.cpp: In function 'int32_t main()':
palindromic.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 1; i <= s.size(); ++i) h[i] = h[i - 1] * 19937 + s[i - 1];
      |                     ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 3 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 39 ms 26440 KB Output is correct
15 Correct 23 ms 22716 KB Output is correct
16 Correct 35 ms 25356 KB Output is correct
17 Correct 26 ms 18564 KB Output is correct