oj.uz

Submission #230589

# Submission time Handle Problem Language Result Execution time Memory
230589 2020-05-10T13:46:16 Z AlexLuchianov Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 620 ms 66820 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
int const sigma = 26;
int const modulo = 1000000007;
int const modulo2 = 998244353;
int pw[2][1 + nmax];

void computepow(){
  pw[0][0] = pw[1][0] = 1;
  for(int i = 1; i <= nmax; i++){
    pw[0][i] = 1LL * pw[0][i - 1] * sigma % modulo;
    pw[1][i] = 1LL * pw[1][i - 1] * sigma % modulo2;
  }
}

class Hash{
public:
  int l;
  int number;
  int number2;
  Hash(char ch = 0){
    if(ch == 0){
      l = 0;
      number = number2 = 0;
    } else {
      l = 1;
      number = ch - 'a';
      number2 = ch - 'a';
    }
  }
  Hash operator + (Hash const &a) const {
    Hash result;
    result.l = l + a.l;
    result.number = (1LL * number * pw[0][a.l] + a.number) % modulo;
    result.number2 = (1LL * number2 * pw[1][a.l] + a.number2) % modulo2;
    return result;
  }
  bool operator == (Hash const &a) const {
    return l == a.l && number == a.number && number2 == a.number2;
  }
};
string s;

int _partition(int from, int to){
  if(to < from)
    return 0;
  Hash f1, f2;
  int d = (to - from + 1);
  for(int i = 1; i * 2 <= d; i++){
    f1 = f1 + s[from];
    from++;
    f2 = Hash(s[to]) + f2;
    to--;

    if(f1 == f2)
      return _partition(from, to) + 2;
  }
  return 1;
}

int solve(){
  cin >> s;
  s = "#" + s;
  int n = s.size() - 1;
  return _partition(1, n);
}

int main()
{
  computepow();
  int t;
  cin >> t;
  for(int testcase = 1; testcase <= t; testcase++)
    cout << solve() << '\n';
  return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8192 KB Output is correct
2 Correct 15 ms 8192 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 15 ms 8192 KB Output is correct
5 Correct 15 ms 8192 KB Output is correct
6 Correct 15 ms 8192 KB Output is correct
7 Correct 15 ms 8192 KB Output is correct
8 Correct 15 ms 8192 KB Output is correct
9 Correct 15 ms 8192 KB Output is correct
10 Correct 20 ms 8704 KB Output is correct
11 Correct 18 ms 8576 KB Output is correct
12 Correct 20 ms 8320 KB Output is correct
13 Correct 19 ms 8448 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8192 KB Output is correct
2 Correct 15 ms 8192 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 15 ms 8192 KB Output is correct
5 Correct 15 ms 8192 KB Output is correct
6 Correct 15 ms 8192 KB Output is correct
7 Correct 15 ms 8192 KB Output is correct
8 Correct 15 ms 8192 KB Output is correct
9 Correct 15 ms 8192 KB Output is correct
10 Correct 20 ms 8704 KB Output is correct
11 Correct 18 ms 8576 KB Output is correct
12 Correct 20 ms 8320 KB Output is correct
13 Correct 19 ms 8448 KB Output is correct
14 Correct 620 ms 66820 KB Output is correct
15 Correct 321 ms 45136 KB Output is correct
16 Correct 503 ms 21160 KB Output is correct
17 Correct 338 ms 26652 KB Output is correct