oj.uz

Submission #469860

# Submission time Handle Problem Language Result Execution time Memory
469860 2021-09-02T07:01:01 Z xiaowuc1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 367 ms 27808 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;


template <int MOD_> struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

private:
  using ll = long long;

  int v;

  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  }

public:

  modnum() : v(0) {}
  modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  explicit operator int() const { return v; }
  friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

  friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

  modnum inv() const {
    modnum res;
    res.v = minv(v, MOD);
    return res;
  }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD-v : 0;
    return res;
  }

  modnum operator- () const {
    return neg();
  }
  modnum operator+ () const {
    return modnum(*this);
  }

  modnum& operator ++ () {
    v ++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator -- () {
    if (v == 0) v = MOD;
    v --;
    return *this;
  }
  modnum& operator += (const modnum& o) {
    v += o.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  modnum& operator -= (const modnum& o) {
    v -= o.v;
    if (v < 0) v += MOD;
    return *this;
  }
  modnum& operator *= (const modnum& o) {
    v = int(ll(v) * ll(o.v) % MOD);
    return *this;
  }
  modnum& operator /= (const modnum& o) {
    return *this *= o.inv();
  }

  friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template <typename T> T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

struct rabinkarp {
  typedef modnum<998244353> mnum1;
  typedef modnum<1000000007> mnum2;
  typedef pair<mnum1, mnum2> shash;
  int STRING_SZ;
  const mnum1 HASH1 = 3137;
  const mnum2 HASH2 = 1009;
  vector<shash> hashes;
  vector<mnum1> hash1pows;
  vector<mnum2> hash2pows;
  rabinkarp() {}
  rabinkarp(const string& s) {
    STRING_SZ = sz(s);
    hash1pows.resize(STRING_SZ+1);
    hash1pows[0] = 1;
    for(int i = 1; i <= STRING_SZ; i++) hash1pows[i] = hash1pows[i-1] * HASH1;
    hash2pows.resize(STRING_SZ+1);
    hash2pows[0] = 1;
    for(int i = 1; i <= STRING_SZ; i++) hash2pows[i] = hash2pows[i-1] * HASH2;
    hashes.resize(STRING_SZ+1);
    for(int i = 0; i < sz(s); i++) {
      hashes[i+1].first = hashes[i].first * HASH1 + s[i];
      hashes[i+1].second = hashes[i].second * HASH2 + s[i];
    }
  }
  inline pii getHash(int lhs, int rhs) {
    // [lhs, rhs)
    mnum1 a = hashes[rhs].first - hashes[lhs].first * hash1pows[rhs-lhs];
    mnum2 b = hashes[rhs].second - hashes[lhs].second * hash2pows[rhs-lhs];
    return {(int)a, (int)b};
  }
  inline pii hashStr(const string& s) {
    mnum1 a = 0;
    mnum2 b = 0;
    for(auto x: s) {
      a = a * HASH1 + x;
      b = b * HASH2 + x;
    }
    return {(int)a, (int)b};
  }
};

void rsolve() {
  string s;
  cin >> s;
  rabinkarp rk(s);
  int ret = 0;
  int lhs = 0;
  int rhs = sz(s);
  while(lhs < rhs) {
    int a = 1;
    bool found = false;
    while(lhs + a <= rhs - a) {
      if(rk.getHash(lhs, lhs+a) == rk.getHash(rhs-a, rhs)) {
        lhs += a;
        rhs -= a;
        ret += 2;
        found = true;
        break;
      }
      a++;
    }
    if(!found) {
      ret++;
      break;
    }
  }
  cout << ret << "\n";
}

void solve() {
  int t;
  cin >> t;
  while(t--) rsolve();
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 2 ms 500 KB Output is correct
12 Correct 4 ms 552 KB Output is correct
13 Correct 3 ms 540 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 2 ms 500 KB Output is correct
12 Correct 4 ms 552 KB Output is correct
13 Correct 3 ms 540 KB Output is correct
14 Correct 367 ms 27808 KB Output is correct
15 Correct 191 ms 22440 KB Output is correct
16 Correct 336 ms 25964 KB Output is correct
17 Correct 191 ms 15144 KB Output is correct