제출 #469860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469860		xiaowuc1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	367 ms	27808 KiB

palindromic

#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 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40