oj.uz

답안 #698509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698509 2023-02-13T16:30:51 Z dattranxxx Palindromic Partitions (CEOI17_palindromic) C++11
100 / 100
 174 ms 44292 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int M = 1e9 + 696969;
struct Hash {
  int x; unsigned long long y;
  Hash(int x = 0): x(x), y(x) {}
  friend Hash operator + (Hash u, const Hash& v) {
    u.x += v.x; u.y += v.y;
    if (u.x >= M) u.x -= M;
    return u;
  }
  friend Hash operator - (Hash u, const Hash& v) {
    u.x -= v.x; u.y -= v.y;
    if (u.x < 0) u.x += M;
    return u;
  }
  friend Hash operator * (Hash u, const Hash& v) {
    u.x = 1LL * u.x * v.x % M;
    u.y = u.y * v.y;
    return u;
  }
  friend bool operator == (const Hash& u, const Hash& v) {
    return u.x == v.x && u.y == v.y;
  }
};

using ull = Hash;

const int N = 1e6 + 5;

string s;

ull h[N], pw[N], base = 31;

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

int n;

int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  pw[0] = 1;
  for (int i = 1; i < N; ++i) {
    pw[i] = pw[i - 1] * base;
  }
  
  int T; cin >> T;
  while (T--) {
    cin >> s; 
    n = s.size();
    s = ' ' + s;
    
    for (int i = 1; i <= n; ++i) {
      h[i] = h[i - 1] * base + s[i] - 'a' + 1;
    }
    
    int last = 1, res = 0;
    for (int i = 1; i <= n / 2; ++i) {
      if (get(last, i) == get(n - i + 1, n - last + 1)) {
        res += 2;
        last = i + 1;
      }
    }
    if (last <= (n + 1) / 2) {
      res += 1;
    }
    cout << res << '\n';
    
  }
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 19 ms 31576 KB Output is correct
3 Correct 17 ms 31520 KB Output is correct
4 Correct 18 ms 31572 KB Output is correct
5 Correct 18 ms 31552 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 19 ms 31576 KB Output is correct
3 Correct 17 ms 31520 KB Output is correct
4 Correct 18 ms 31572 KB Output is correct
5 Correct 18 ms 31552 KB Output is correct
6 Correct 22 ms 31508 KB Output is correct
7 Correct 18 ms 31640 KB Output is correct
8 Correct 20 ms 31640 KB Output is correct
9 Correct 18 ms 31572 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 19 ms 31576 KB Output is correct
3 Correct 17 ms 31520 KB Output is correct
4 Correct 18 ms 31572 KB Output is correct
5 Correct 18 ms 31552 KB Output is correct
6 Correct 22 ms 31508 KB Output is correct
7 Correct 18 ms 31640 KB Output is correct
8 Correct 20 ms 31640 KB Output is correct
9 Correct 18 ms 31572 KB Output is correct
10 Correct 20 ms 31668 KB Output is correct
11 Correct 18 ms 31628 KB Output is correct
12 Correct 20 ms 31732 KB Output is correct
13 Correct 19 ms 31700 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 19 ms 31576 KB Output is correct
3 Correct 17 ms 31520 KB Output is correct
4 Correct 18 ms 31572 KB Output is correct
5 Correct 18 ms 31552 KB Output is correct
6 Correct 22 ms 31508 KB Output is correct
7 Correct 18 ms 31640 KB Output is correct
8 Correct 20 ms 31640 KB Output is correct
9 Correct 18 ms 31572 KB Output is correct
10 Correct 20 ms 31668 KB Output is correct
11 Correct 18 ms 31628 KB Output is correct
12 Correct 20 ms 31732 KB Output is correct
13 Correct 19 ms 31700 KB Output is correct
14 Correct 174 ms 43220 KB Output is correct
15 Correct 105 ms 38624 KB Output is correct
16 Correct 163 ms 44292 KB Output is correct
17 Correct 100 ms 37736 KB Output is correct