• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/528/2A.cpp version [294b894277ee8322]

                                                                                        >     1  #include <iostream>
                                                                                        >     2  #include <sstream>
                                                                                        >     3  #include <iomanip>
                                                                                        >     4  #include <vector>
                                                                                        >     5  #include <string>
                                                                                        >     6  #include <map>
                                                                                        >     7  #include <set>
                                                                                        >     8  #include <algorithm>
                                                                                        >     9  #include <numeric>
                                                                                        >    10  #include <iterator>
                                                                                        >    11  #include <functional>
                                                                                        >    12  #include <complex>
                                                                                        >    13  #include <queue>
                                                                                        >    14  #include <stack>
                                                                                        >    15  #include <cmath>
                                                                                        >    16  #include <cassert>
                                                                                        >    17  #include <cstring>
                                                                                        >    18  #ifdef __GNUC__
                                                                                        >    19  #include <ext/hash_map>
                                                                                        >    20  #define unordered_map __gnu_cxx::hash_map
                                                                                        >    21  #else
                                                                                        >    22  #include <unordered_map>
                                                                                        >    23  #endif
                                                                                        >    24  using namespace std;
                                                                                        >    25  typedef long long LL;
                                                                                        >    26  typedef complex<double> CMP;
                                                                                        >    27  
                                                                                        >    28  class MinCostPalindrome { public:
                                                                                        >    29          int getMinimum(string s, int oCost, int xCost)
                                                                                        >    30          {
                                                                                        >    31                  int total = 0;
                                                                                        >    32                  for(int i=0; i<s.size()-i-1; ++i)
                                                                                        >    33                          if( s[i]=='o' && s[s.size()-i-1]=='x' )
                                                                                        >    34                                  return -1;
                                                                                        >    35                          else if( s[i]=='x' && s[s.size()-i-1]=='o' )
                                                                                        >    36                                  return -1;
                                                                                        >    37                          else if( s[i]=='o' && s[s.size()-i-1]=='?'
                                                                                        >    38                                    || s[i]=='?' && s[s.size()-i-1]=='o' )
                                                                                        >    39                                  total += oCost;
                                                                                        >    40                          else if( s[i]=='x' && s[s.size()-i-1]=='?'
                                                                                        >    41                                    || s[i]=='?' && s[s.size()-i-1]=='x' )
                                                                                        >    42                                  total += xCost;
                                                                                        >    43                          else if( s[i]=='?' && s[s.size()-i-1]=='?' )
                                                                                        >    44                                  total += min(oCost, xCost) * 2;
                                                                                        >    45                  if( s.size()%2 == 1 && s[s.size()/2]=='?' )
                                                                                        >    46                          total += min(oCost, xCost);
                                                                                        >    47                  return total;
                                                                                        >    48          }
                                                                                        >    49  };
                                                                                        >    50  
                                                                                        >    51  // BEGIN CUT HERE
                                                                                        >    52  #include <ctime>
                                                                                        >    53  double start_time; string timer()
                                                                                        >    54   { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000)
                                                                                        >    55  template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
                                                                                        >    56   { os << "{ ";
                                                                                        >    57     for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
                                                                                        >    58     os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return 
                                                                                        >    59  void verify_case(const int& Expected, const int& Received) {
                                                                                        >    60   bool ok = (Expected == Received);
                                                                                        >    61   if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer()
                                                                                        >    62   cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' 
                                                                                        >    63  #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(
                                                                                        >    64  #define END      verify_case(_, MinCostPalindrome().getMinimum(s, oCost, xCost))
                                                                                        >    65  int main(){
                                                                                        >    66  
                                                                                        >    67  CASE(0)
                                                                                        >    68          string s = "oxo?xox?";
                                                                                        >    69          int oCost = 3;
                                                                                        >    70          int xCost = 5;
                                                                                        >    71          int _ = 8;
                                                                                        >    72  END
                                                                                        >    73  CASE(1)
                                                                                        >    74          string s = "x??x";
                                                                                        >    75          int oCost = 9;
                                                                                        >    76          int xCost = 4;
                                                                                        >    77          int _ = 8;
                                                                                        >    78  END
                                                                                        >    79  CASE(2)
                                                                                        >    80          string s = "ooooxxxx";
                                                                                        >    81          int oCost = 12;
                                                                                        >    82          int xCost = 34;
                                                                                        >    83          int _ = -1;
                                                                                        >    84  END
                                                                                        >    85  CASE(3)
                                                                                        >    86          string s = "oxoxooxxxxooxoxo";
                                                                                        >    87          int oCost = 7;
                                                                                        >    88          int xCost = 4;
                                                                                        >    89          int _ = 0;
                                                                                        >    90  END
                                                                                        >    91  CASE(4)
                                                                                        >    92          string s = "?o";
                                                                                        >    93          int oCost = 6;
                                                                                        >    94          int xCost = 2;
                                                                                        >    95          int _ = 6;
                                                                                        >    96  END
                                                                                        >    97  CASE(5)
                                                                                        >    98          string s = "????????????????????";
                                                                                        >    99          int oCost = 50;
                                                                                        >   100          int xCost = 49;
                                                                                        >   101          int _ = 980;
                                                                                        >   102  END
                                                                                        >   103  CASE(6)
                                                                                        >   104          string s = "o??oxxo?xoox?ox??x??" ;
                                                                                        >   105          int oCost = 3;
                                                                                        >   106          int xCost = 10;
                                                                                        >   107          int _ = 38;
                                                                                        >   108  END
                                                                                        >   109  /*
                                                                                        >   110  CASE(7)
                                                                                        >   111          string s = ;
                                                                                        >   112          int oCost = ;
                                                                                        >   113          int xCost = ;
                                                                                        >   114          int _ = ;
                                                                                        >   115  END
                                                                                        >   116  CASE(8)
                                                                                        >   117          string s = ;
                                                                                        >   118          int oCost = ;
                                                                                        >   119          int xCost = ;
                                                                                        >   120          int _ = ;
                                                                                        >   121  END
                                                                                        >   122  */
                                                                                        >   123  }
                                                                                        >   124  // END CUT HERE