Submission #2070901


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

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

#define pb push_back
#define fr first
#define sc second

int main(){
	string s;
	cin >> s;
	
	map<int,int> M;
	int sum = 0;
	M.insert(P(0,1));
	for(int j = 0 ; j < 26 ; j ++)M.insert(P(1<<j,1));
	for(int i = 0 ; i < s.size() ; i ++){
		sum ^= (1<<(s[i]-'a'));
		int ans = M[sum];
		for(int j = 0 ; j < 26 ; j ++){
			if(M.find(sum^(1<<j)) == M.end()){
				M[sum^(1<<j)] = ans+1;
			}
			else M[sum^(1<<j)] = min( M[sum^(1<<j)] , ans+1 );
		}
	}
	cout << M[sum] << endl;
}

Submission Info

Submission Time
Task D - Yet Another Palindrome Partitioning
User yokozuna57
Language C++14 (GCC 5.4.1)
Score 700
Code Size 697 Byte
Status
Exec Time 2980 ms
Memory 204292 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 700 / 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 2154 ms 147588 KB
1_09.txt 183 ms 644 KB
1_10.txt 233 ms 644 KB
1_11.txt 194 ms 640 KB
1_12.txt 115 ms 640 KB
1_13.txt 134 ms 640 KB
1_14.txt 165 ms 640 KB
1_15.txt 457 ms 640 KB
1_16.txt 639 ms 640 KB
1_17.txt 762 ms 640 KB
1_18.txt 855 ms 640 KB
1_19.txt 929 ms 644 KB
1_20.txt 1022 ms 900 KB
1_21.txt 1148 ms 1284 KB
1_22.txt 1275 ms 1924 KB
1_23.txt 1388 ms 3332 KB
1_24.txt 1466 ms 5764 KB
1_25.txt 1603 ms 10372 KB
1_26.txt 1757 ms 18820 KB
1_27.txt 2016 ms 32388 KB
1_28.txt 2142 ms 48388 KB
1_29.txt 2303 ms 62724 KB
1_30.txt 2593 ms 76036 KB
1_31.txt 2730 ms 94852 KB
1_32.txt 2896 ms 122628 KB
1_33.txt 2980 ms 151172 KB
1_34.txt 2960 ms 170756 KB
1_35.txt 2935 ms 189060 KB
1_36.txt 2718 ms 193412 KB
1_37.txt 2880 ms 204292 KB
1_38.txt 1749 ms 20228 KB
1_39.txt 1704 ms 20228 KB
1_40.txt 1728 ms 20356 KB
1_41.txt 1672 ms 19844 KB
1_42.txt 1598 ms 13572 KB
1_43.txt 1576 ms 13572 KB
1_44.txt 1562 ms 13572 KB
1_45.txt 1545 ms 13572 KB
1_46.txt 1423 ms 9476 KB
1_47.txt 1326 ms 8964 KB
1_48.txt 1389 ms 9220 KB
1_49.txt 1411 ms 9348 KB
1_50.txt 1281 ms 6532 KB
1_51.txt 1275 ms 6660 KB
1_52.txt 1206 ms 6532 KB
1_53.txt 1249 ms 6532 KB
1_54.txt 1135 ms 4868 KB
1_55.txt 1126 ms 4740 KB
1_56.txt 1149 ms 4868 KB
1_57.txt 1092 ms 4868 KB
1_58.txt 1015 ms 3588 KB
1_59.txt 963 ms 3588 KB
1_60.txt 1009 ms 3588 KB
1_61.txt 952 ms 3588 KB
1_62.txt 899 ms 2692 KB
1_63.txt 907 ms 2692 KB
1_64.txt 915 ms 2692 KB
1_65.txt 896 ms 2692 KB
1_66.txt 824 ms 1924 KB
1_67.txt 784 ms 2052 KB
1_68.txt 843 ms 2052 KB
1_69.txt 776 ms 2052 KB
1_70.txt 777 ms 1668 KB
1_71.txt 764 ms 1668 KB
1_72.txt 766 ms 1668 KB
1_73.txt 746 ms 1668 KB
1_74.txt 710 ms 1412 KB
1_75.txt 679 ms 1540 KB
1_76.txt 712 ms 1412 KB
1_77.txt 677 ms 1412 KB