oj.uz

Submission #593769

# Submission time Handle Problem Language Result Execution time Memory
593769 2022-07-11T15:01:19 Z cadmiumsky Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 398 ms 50116 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int nmax = 1e6 + 5;

#define int ll
#define hash mamamare
const int mod = 998244853;
int p[nmax][2];

struct hash {
  int v[2], len;
  hash() {v[0] = v[1] = len = 0; }
  hash(char ch) {v[0] = v[1] = ch - 'a', len = 1;}
  hash(int a, int b, int c) {v[0] = a, v[1] = b, len = c; }
  hash operator + (const hash& other) {
    return hash((v[0] * p[other.len][0] + other.v[0]) % mod, 
                (v[1] * p[other.len][1] + other.v[1]) % mod,
                 len + other.len);
  }
  hash operator - (const hash& other) {
    return hash((v[0] - p[len - other.len][0] * other.v[0] % mod + mod) % mod,
                (v[1] - p[len - other.len][1] * other.v[1] % mod + mod) % mod,
                len - other.len);
  }
  bool operator == (const hash& other) {
    return tuple<int,int,int>{v[0], v[1], len} == tuple<int,int,int>{other.v[0], other.v[1], other.len};
  }
};
#undef int

void testcase() {
  string s;
  int n;
  cin >> s;
  n = s.size();
  s = "$" + s;
  vector<hash> vec(n + 1);
  for(int i = 1; i <= n; i++)
    vec[i] = vec[i - 1] + hash(s[i]);
  auto gethash = [&](int l, int r) {
    return vec[r] - vec[l - 1];
  };
  int l = 1, r = n, len = 0, cnt = 0;
  while(l < r) {
    len++;
    if(gethash(l - len + 1, l) == gethash(r, r + len - 1)) {
      cnt += 2;
      //cerr << gethash(l - len + 1, l).v[0] << ' ' << l - len + 1 << ' ' << l << '\t' << r  << ' ' << r + len - 1 << '\n';
      len = 0;
      
    }
    l++;
    r--;
  }
  if(len != 0 || l == r)
    cnt++;
  cout << cnt << '\n';
}
 

int main() {
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  //mt19937 rng(69420);
  p[0][1] = p[0][0] = 1;
  p[1][1] = rng() % (mod - 5) + 3;
  p[1][0] = rng() % (mod - 5) + 3;
  for(int i = 2; i < nmax; i++)
    p[i][0] = p[i - 1][0] * p[1][0] % mod,
    p[i][1] = p[i - 1][1] * p[1][1] % mod;
  //cerr << p[1][1] << ' ' << p[1][0] << '\n';
  //cerr << p[2][1] << ' ' << p[2][0] << '\n';
  int t;
  cin >> t;
  while(t--)
    testcase();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15956 KB Output is correct
2 Correct 15 ms 15868 KB Output is correct
3 Correct 14 ms 15940 KB Output is correct
4 Correct 14 ms 15956 KB Output is correct
5 Correct 16 ms 15952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15956 KB Output is correct
2 Correct 15 ms 15868 KB Output is correct
3 Correct 14 ms 15940 KB Output is correct
4 Correct 14 ms 15956 KB Output is correct
5 Correct 16 ms 15952 KB Output is correct
6 Correct 14 ms 15956 KB Output is correct
7 Correct 14 ms 15956 KB Output is correct
8 Correct 14 ms 15952 KB Output is correct
9 Correct 13 ms 15968 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15956 KB Output is correct
2 Correct 15 ms 15868 KB Output is correct
3 Correct 14 ms 15940 KB Output is correct
4 Correct 14 ms 15956 KB Output is correct
5 Correct 16 ms 15952 KB Output is correct
6 Correct 14 ms 15956 KB Output is correct
7 Correct 14 ms 15956 KB Output is correct
8 Correct 14 ms 15952 KB Output is correct
9 Correct 13 ms 15968 KB Output is correct
10 Correct 18 ms 16248 KB Output is correct
11 Correct 15 ms 16284 KB Output is correct
12 Correct 18 ms 16336 KB Output is correct
13 Correct 17 ms 16224 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15956 KB Output is correct
2 Correct 15 ms 15868 KB Output is correct
3 Correct 14 ms 15940 KB Output is correct
4 Correct 14 ms 15956 KB Output is correct
5 Correct 16 ms 15952 KB Output is correct
6 Correct 14 ms 15956 KB Output is correct
7 Correct 14 ms 15956 KB Output is correct
8 Correct 14 ms 15952 KB Output is correct
9 Correct 13 ms 15968 KB Output is correct
10 Correct 18 ms 16248 KB Output is correct
11 Correct 15 ms 16284 KB Output is correct
12 Correct 18 ms 16336 KB Output is correct
13 Correct 17 ms 16224 KB Output is correct
14 Correct 398 ms 50116 KB Output is correct
15 Correct 241 ms 45468 KB Output is correct
16 Correct 373 ms 48732 KB Output is correct
17 Correct 276 ms 33920 KB Output is correct