Submission #795311

#	Time	Username	Problem	Language	Result	Execution time	Memory
795311		cig32	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	0 ms	212 KiB

palindromic

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }

//untested

struct hash_string {
  const int fac = 2017;
  const int MOD = 1734232211; // prime!
  vector<int> pau, ps; // all indices 0-based
  int n;
  void init(string s) {
    n = s.size();
    pau.push_back(1);
    for(int i=1; i<=n; i++) {
      pau.push_back((pau[i-1] * fac) % MOD);
    }
    ps.push_back(s[0]);
    for(int i=1; i<n; i++) {
      ps.push_back((ps[i-1] * fac + s[i]) % MOD);
    }
  }
  int eval(int l, int r) {
    return (ps[r] - (l == 0 ? 0 : (ps[l-1] * pau[r-l+1]) % MOD) + MOD) % MOD;
  }
};
void solve(int tc) {
  hash_string hst;
  string bruh;
  cin >> bruh;
  int no = 0;
  if(bruh.size() & 1) {
    string x;
    for(int i=0; i<bruh.size()/2; i++) x += bruh[i];
    x += bruh[bruh.size() / 2];
    x += bruh[bruh.size() / 2];
    for(int i=bruh.size()/2+1; i<bruh.size(); i++) x += bruh[i];
    bruh = x;
    no = 1;
  }
  hst.init(bruh);
  int ans = 0, n = bruh.size();
  int cn = 0;
  for(int i=0; i<n/2; i++) {
    int j = i;
    while(hst.eval(i, j) != hst.eval(n-1-j, n-1-i) && j+1 < n/2) j++;
    if(hst.eval(i, j) == hst.eval(n-1-j, n-1-i)) {
      cn += 2;
      ans = max(ans, cn);
    }
    else {
      ans = max(ans, cn + 1);
    }
    i = j;
  }
  cout << min(n - no, ans) << '\n';
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Compilation message (stderr)

palindromic.cpp: In function 'void solve(long long int)':
palindromic.cpp:53:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0; i<bruh.size()/2; i++) x += bruh[i];
      |                  ~^~~~~~~~~~~~~~
palindromic.cpp:56:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=bruh.size()/2+1; i<bruh.size(); i++) x += bruh[i];
      |                                ~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40