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

Added SRM/671-U/1A.cpp version [71a7603b4167a67f]

                                                                                        >     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 <tuple>
                                                                                        >    18  using namespace std;
                                                                                        >    19  typedef long long LL;
                                                                                        >    20  typedef complex<double> CMP;
                                                                                        >    21  
                                                                                        >    22  static const unsigned MODVAL = 1000000007;
                                                                                        >    23  struct mint
                                                                                        >    24  {
                                                                                        >    25          unsigned val;
                                                                                        >    26          mint():val(0){}
                                                                                        >    27          mint(int      x):val(x%MODVAL) {}
                                                                                        >    28          mint(unsigned x):val(x%MODVAL) {}
                                                                                        >    29          mint(LL       x):val(x%MODVAL) {}
                                                                                        >    30  };
                                                                                        >    31  mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
                                                                                        >    32  mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
                                                                                        >    33  mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
                                                                                        >    34  mint operator+(mint x, mint y) { return x+=y; }
                                                                                        >    35  mint operator-(mint x, mint y) { return x-=y; }
                                                                                        >    36  mint operator*(mint x, mint y) { return x*=y; }
                                                                                        >    37  
                                                                                        >    38  template<typename T>
                                                                                        >    39  struct DP3
                                                                                        >    40  {
                                                                                        >    41          int N1, N2, N3;
                                                                                        >    42          vector<T> data;
                                                                                        >    43          DP3(int N1, int N2, int N3, const T& t = T())
                                                                                        >    44                  : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()
                                                                                        >    45          T& operator()(int i1, int i2, int i3)
                                                                                        >    46                  { return data[ ((i1*N2)+i2)*N3+i3 ]; }
                                                                                        >    47          void swap(DP3& rhs)
                                                                                        >    48                  { data.swap(rhs.data); }
                                                                                        >    49  };
                                                                                        >    50  
                                                                                        >    51  class BearCries { public:
                                                                                        >    52          int count(string message)
                                                                                        >    53          {
                                                                                        >    54                  const int N = message.size();
                                                                                        >    55                  DP3<int> dp(N, N, N, -1);
                                                                                        >    56                  function<int(int,int,int)> rec;
                                                                                        >    57                  rec = [&](int i, int s, int su) {
                                                                                        >    58                          if(i == N)
                                                                                        >    59                                  return (s==0 && su==0 ? 1 : 0);
                                                                                        >    60                          if(dp(i,s,su) != -1)
                                                                                        >    61                                  return dp(i,s,su);
                                                                                        >    62                          mint total = 0;
                                                                                        >    63                          if(message[i]==';') {
                                                                                        >    64                                  total += rec(i+1, s+1, su);
                                                                                        >    65                                  if(su) total += mint(rec(i+1, s, su-1)) * su;
                                                                                        >    66                          } else {
                                                                                        >    67                                  if(s) total += mint(rec(i+1, s-1, su+1)) * s;
                                                                                        >    68                                  if(su) total += mint(rec(i+1, s, su)) * su;
                                                                                        >    69                          }
                                                                                        >    70                          return dp(i,s,su) = total.val;
                                                                                        >    71                  };
                                                                                        >    72                  return rec(0, 0, 0);
                                                                                        >    73          }
                                                                                        >    74  };
                                                                                        >    75  
                                                                                        >    76  // BEGIN CUT HERE
                                                                                        >    77  #include <ctime>
                                                                                        >    78  double start_time; string timer()
                                                                                        >    79   { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000)
                                                                                        >    80  template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
                                                                                        >    81   { os << "{ ";
                                                                                        >    82     for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
                                                                                        >    83     os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return 
                                                                                        >    84  void verify_case(const int& Expected, const int& Received) {
                                                                                        >    85   bool ok = (Expected == Received);
                                                                                        >    86   if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer()
                                                                                        >    87   cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' 
                                                                                        >    88  #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(
                                                                                        >    89  #define END      verify_case(_, BearCries().count(message));}
                                                                                        >    90  int main(){
                                                                                        >    91  
                                                                                        >    92  CASE(0)
                                                                                        >    93          string message = ";_;;_____;";
                                                                                        >    94          int _ = 2;
                                                                                        >    95  END
                                                                                        >    96  CASE(1)
                                                                                        >    97          string message = ";;;___;;;";
                                                                                        >    98          int _ = 36;
                                                                                        >    99  END
                                                                                        >   100  CASE(2)
                                                                                        >   101          string message = "_;__;";
                                                                                        >   102          int _ = 0;
                                                                                        >   103  END
                                                                                        >   104  CASE(3)
                                                                                        >   105          string message = ";_____________________________________;";
                                                                                        >   106          int _ = 1;
                                                                                        >   107  END
                                                                                        >   108  CASE(4)
                                                                                        >   109          string message = ";__;____;";
                                                                                        >   110          int _ = 0;
                                                                                        >   111  END
                                                                                        >   112  CASE(5)
                                                                                        >   113          string message = ";_;;__;_;;";
                                                                                        >   114          int _ = 52;
                                                                                        >   115  END
                                                                                        >   116  /*
                                                                                        >   117  CASE(6)
                                                                                        >   118          string message = ;
                                                                                        >   119          int _ = ;
                                                                                        >   120  END
                                                                                        >   121  CASE(7)
                                                                                        >   122          string message = ;
                                                                                        >   123          int _ = ;
                                                                                        >   124  END
                                                                                        >   125  */
                                                                                        >   126  }
                                                                                        >   127  // END CUT HERE

Added SRM/671-U/1B.cpp version [5e009d4a2848484e]

cannot compute difference between binary files