Submission #101377

#	Time	Username	Problem	Language	Result	Execution time	Memory
101377		Milki	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	2 ms	384 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e6 + 5, mod = 1e9 + 7, baza = 1307;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

int h[MAXN], pot[MAXN];

int calc(int x, int y){
  int k = 0;
  if(x) k = mul(h[x - 1], pot[y]);
  return sub(h[x + y - 1], k);
}

void solve(){
  string s; cin >> s;
  h[0] = s[0];
  pot[0] = 1;
  FOR(i, 1, sz(s)){
    h[i] = add( mul(h[i - 1], baza), s[i]);
    pot[i] = mul(pot[i - 1], baza);
  }

  int sol = 0, cnt = 0;
  REP(i, sz(s) / 2){
    cnt ++;

    if( calc(i - cnt + 1, cnt) == calc(sz(s) - i - 1, cnt)){
      sol += 2;
      cnt = 0;
    }
  }
  if(sz(s) % 2) sol ++;
  else if(sz(s) % 2 == 0 && s[sz(s) / 2] != s[sz(s) / 2 + 1]) sol ++;

  cout << sol << "\n";
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  int t; cin >> t;
  while(t --)
    solve();
}

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