Submission #757813

#	Time	Username	Problem	Language	Result	Execution time	Memory
757813		taher	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	693 ms	13144 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while(tt--){
    string ss;cin >> ss;
    int len = ss.length();
    deque<char> a, b;
    int ans = 1;
    unordered_map<char,int>occ;
    unordered_map<char,int>occ2;
    for(int i = 0,r = len-1 ; i < len/2 ; i++,r--){
      a.push_back(ss[i]);
      b.push_front(ss[r]);
      occ[ss[i]]++; occ2[ss[r]]++;
      if(a.back()!=b.back()||a.front()!=b.front())continue;
      bool it = 1;
      for(char j = 'a' ; j<='z' && it; j++){
        if(occ[j]!=occ2[j]){
          it = 0;
          continue;
        }
      }
      if(!it)continue;
      if(a==b){
        ans+=2;
        a.clear() ; b.clear();
        if((i+1)*2-len==0)ans--;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

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