Submission #1704221


Source Code Expand

Copy
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int main(){
  string S;
  cin >> S;
  int l = S.length();
  int C[l][26];
  int ans = 100000000;
  for(int _ = 0; _ < 2; ++_){
    reverse(S.begin(),S.end());
  for(int i = 0; i < l; ++i){
    fill(C[i],C[i]+26,0);
  }
  C[0][S[0]-'a'] = 1;
  for(int i = 1; i < S.length(); ++i){
    for(int j = 0; j < 26; ++j){
      if(j == S[i] - 'a'){
	C[i][S[i]-'a'] = 1 - C[i-1][S[i]-'a'];
      }else{
	C[i][j] = C[i-1][j];
      }
    }
  }
  int t = 0, s = 0, r[26];
  int ans_ = 0;
  fill(r,r+26,0);
  while(s < l){
    bool f = true;
    for(int i = s; i < l; ++i){
      bool k = true;
      for(int j = 0; j < 26; ++j){
	if(C[i][j] - r[j] != 0){
	  k = false;
	  break;
	}
      }
      if(k){
	for(int j = 0; j < 26; ++j){
	  r[j] = C[i][j];
	}
	s = i+1;
	f = false;
	break;
      }
    }
    if(f){
      for(int j = 0; j < 26; ++j){
	r[j] = C[s][j];
      }
      //cout << s << endl;
      ++ans_;
      ++s;
    }
  }
  ans = min(ans,ans_);
  }
  cout << max(ans,1) << endl;
  
  return 0;
}

Submission Info

Submission Time
Task D - Yet Another Palindrome Partitioning
User TAB
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1133 Byte
Status
Exec Time 3156 ms
Memory 20868 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0 / 700 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt, 1_72.txt, 1_73.txt, 1_74.txt, 1_75.txt, 1_76.txt, 1_77.txt
Case Name Status Exec Time Memory
0_00.txt 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
0_03.txt 1 ms 256 KB
1_00.txt 1 ms 256 KB
1_01.txt 1 ms 256 KB
1_02.txt 1 ms 256 KB
1_03.txt 1 ms 256 KB
1_04.txt 1 ms 256 KB
1_05.txt 1 ms 256 KB
1_06.txt 1 ms 256 KB
1_07.txt 1 ms 256 KB
1_08.txt
1_09.txt 36 ms 20868 KB
1_10.txt 39 ms 20868 KB
1_11.txt 57 ms 20868 KB
1_12.txt 41 ms 20100 KB
1_13.txt 41 ms 20868 KB
1_14.txt 40 ms 20612 KB
1_15.txt 41 ms 20740 KB
1_16.txt 38 ms 20740 KB
1_17.txt 39 ms 20868 KB
1_18.txt 38 ms 20612 KB
1_19.txt 37 ms 20612 KB
1_20.txt 38 ms 20484 KB
1_21.txt 36 ms 20868 KB
1_22.txt 38 ms 20740 KB
1_23.txt 37 ms 20740 KB
1_24.txt 36 ms 20740 KB
1_25.txt 37 ms 20868 KB
1_26.txt 38 ms 20228 KB
1_27.txt 49 ms 20740 KB
1_28.txt 44 ms 20740 KB
1_29.txt 73 ms 20740 KB
1_30.txt 73 ms 20612 KB
1_31.txt 116 ms 20356 KB
1_32.txt 233 ms 20740 KB
1_33.txt 237 ms 20868 KB
1_34.txt 382 ms 20356 KB
1_35.txt 1059 ms 20612 KB
1_36.txt 2628 ms 20100 KB
1_37.txt 2132 ms 20612 KB
1_38.txt 40 ms 20740 KB
1_39.txt 48 ms 20868 KB
1_40.txt 49 ms 20868 KB
1_41.txt 52 ms 20740 KB
1_42.txt 40 ms 20740 KB
1_43.txt 56 ms 20868 KB
1_44.txt 48 ms 20740 KB
1_45.txt 55 ms 20740 KB
1_46.txt 41 ms 20868 KB
1_47.txt 47 ms 20740 KB
1_48.txt 50 ms 20740 KB
1_49.txt 59 ms 20740 KB
1_50.txt 43 ms 20740 KB
1_51.txt 43 ms 20868 KB
1_52.txt 39 ms 20740 KB
1_53.txt 61 ms 20868 KB
1_54.txt 43 ms 20740 KB
1_55.txt 48 ms 20868 KB
1_56.txt 49 ms 20868 KB
1_57.txt 56 ms 20868 KB
1_58.txt 42 ms 20868 KB
1_59.txt 46 ms 20868 KB
1_60.txt 43 ms 20740 KB
1_61.txt 50 ms 20868 KB
1_62.txt 38 ms 20868 KB
1_63.txt 47 ms 20740 KB
1_64.txt 47 ms 20868 KB
1_65.txt 48 ms 20868 KB
1_66.txt 47 ms 20868 KB
1_67.txt 41 ms 20868 KB
1_68.txt 43 ms 20740 KB
1_69.txt 44 ms 20740 KB
1_70.txt 47 ms 20740 KB
1_71.txt 46 ms 20612 KB
1_72.txt 46 ms 20740 KB
1_73.txt 43 ms 20868 KB
1_74.txt 41 ms 20868 KB
1_75.txt 48 ms 20740 KB
1_76.txt 42 ms 20740 KB
1_77.txt 44 ms 20740 KB