TC SRM 712 Div2

// BEGIN CUT HERE

#include <conio.h>
#include <sstream>
/*
*/
 #define debuging
#ifdef debuging
#define FIN  {freopen("new.in" , "r" , stdin) ;}
#define FOUT {freopen("new.out" , "w" , stdout) ;}
#define OUT(x)  {cout<< #x << "  : " << x <<endl ;}
#define ERR(x)  {cout<<"#error: "<< x ; while(1) ;}
#endif
// END CUT HERE
#ifndef debuging
#define FIN  ;
#define FOUT ;
#define OUT(x)  ;
#define ERR(x)  ;
#endif
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
using namespace std ;
#define For(i , n) for(int i = 0 ; i < (n) ; ++i)
#define SZ(x)  (int)((x).size())
typedef long long lint ;
const int maxint = -1u>>2 ;
const double eps = 1e-6 ;
 

class MakePalindrome
{
 public:
 vector <string> constructMinimal(string card)
 {
    int len = card.size();
    int num[30] = {0};
    for(int i = 0; i < len; ++i) {
        num[card[i] - 'a'] ++;
    }
    int odd, even;
    odd = even = 0;
    for(int i = 0; i < 26; ++i) {
        if(num[i] && num[i]&1) odd++;
        else if(num[i] && !(num[i]&1)) even++;
    }
    vector<string> ans;
    ans.clear();
    if(odd == 0 && even) {
        
        string a;
        for(int i = 0; i < 26; ++i) {
            if(num[i]) {
                int cnt = num[i] / 2;
                while(cnt--) a += i + 'a';
            }
        }
        for(int i = 25; i >= 0; --i) {
            if(num[i]) {
                int cnt = num[i] / 2;
                while(cnt--) a += i + 'a';
            }
        }
        
        ans.push_back(a);
    }
    else {
        string a;
        for(int i = 0; i < 26; ++i) {
            if(num[i] > 0&& !(num[i]&1)) {
                int cnt = num[i] / 2;
                while(cnt--) a += i + 'a';
            }
            
        }
        for(int i = 0; i < 26; ++i) {
            if(num[i] > 0&& num[i]&1) {
                while(num[i]--) a += i + 'a';
                break;
            } 
        }
        for(int i = 25; i >= 0; --i) {
            if(num[i] > 0&& !(num[i]&1)) {
                int cnt = num[i] / 2;
                while(cnt--) a += i + 'a';
            }
        }
        ans.push_back(a);
        //cout << a<<endl;
        //cout << ans[0]<<endl;
        a.clear();
        //cout << ans[0]<< endl;
        for(int i = 0; i < 26; ++i) {
            //cout << ans[0]<<endl;
            if(num[i] > 0  && num[i]&1) {
                //cout << num[i]<<endl;
                while(num[i]--) 
                    a += i +'a';
                //cout << a;
                ans.push_back(a);
                a.clear();
            }
        }
    }
    
  return vector<string> (ans);
 }
 
 
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const vector <string> &Expected, const vector <string> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }
	void test_case_0() { string Arg0 = "abbaa"; string Arr1[] = {"ababa" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, constructMinimal(Arg0)); }
	void test_case_1() { string Arg0 = "abc"; string Arr1[] = {"a", "b", "c" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, constructMinimal(Arg0)); }
	void test_case_2() { string Arg0 = "aaabbbccc"; string Arr1[] = {"aba", "bcb", "cac" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, constructMinimal(Arg0)); }
	void test_case_3() { string Arg0 = "topcoder"; string Arr1[] = {"oco", "d", "e", "p", "r", "t" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(3, Arg1, constructMinimal(Arg0)); }
	void test_case_4() { string Arg0 = "z"; string Arr1[] = {"z" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(4, Arg1, constructMinimal(Arg0)); }

// END CUT HERE

};
// BEGIN CUT HERE
int main(){
 MakePalindrome ___test;
 ___test.run_test(-1);
 getch() ;
 return 0;
}
// END CUT HERE