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

Added SRM/533-U/1A.cpp version [a610cb1c6934038d]

            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 CasketOfStar { public:
           29  + int maxEnergy(vector <int> weight)
           30  + {
           31  +  return rec(weight, 0, weight.size()-1);
           32  + }
           33  +
           34  + map<pair<int,int>, int> memo;
           35  + int rec(const vector<int>& w, int L, int R)
           36  + {
           37  +  if( L+1 == R )
           38  +   return 0;
           39  +  pair<int,int> key(L,R);
           40  +  if( memo.count(key) )
           41  +   return memo[key];
           42  +  int best = 0;
           43  +  for(int C=L+1; C<R; ++C)
           44  +   best = max(best, rec(w, L, C) + rec(w, C, R));
           45  +  return memo[key] = best + w[L]*w[R];
           46  + }
           47  +};
           48  +
           49  +// BEGIN CUT HERE
           50  +#include <ctime>
           51  +double start_time; string timer()
           52  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           53  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           54  + { os << "{ ";
           55  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           56  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           57  +void verify_case(const int& Expected, const int& Received) {
           58  + bool ok = (Expected == Received);
           59  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           60  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           61  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           62  +#define END  verify_case(_, CasketOfStar().maxEnergy(weight));}
           63  +int main(){
           64  +
           65  +CASE(0)
           66  + int weight_[] = {1,2,3,4};
           67  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           68  + int _ = 12;
           69  +END
           70  +CASE(1)
           71  + int weight_[] = {100,2,1,3,100};
           72  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           73  + int _ = 10400;
           74  +END
           75  +CASE(2)
           76  + int weight_[] = {2,2,7,6,90,5,9};
           77  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           78  + int _ = 1818;
           79  +END
           80  +CASE(3)
           81  + int weight_[] = {477,744,474,777,447,747,777,474};
           82  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           83  + int _ = 2937051;
           84  +END
           85  +CASE(4)
           86  + int weight_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
           87  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           88  + int _ = 13;
           89  +END
           90  +/*
           91  +CASE(5)
           92  + int weight_[] = ;
           93  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           94  + int _ = ;
           95  +END
           96  +CASE(6)
           97  + int weight_[] = ;
           98  +   vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_));
           99  + int _ = ;
          100  +END
          101  +*/
          102  +}
          103  +// END CUT HERE

Added SRM/533-U/1B.cpp version [e5788b934fa2273e]

            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  +struct UnionFind
           29  +{
           30  + vector<int> uf, sz;
           31  + int nc;
           32  +
           33  + UnionFind(int N): uf(N), sz(N,1), nc(N)
           34  +  { for(int i=0; i<N; ++i) uf[i] = i; }
           35  + int size()
           36  +  { return nc; }
           37  + int Find(int a)
           38  +  { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
           39  + bool Union(int a, int b)
           40  +  {
           41  +   a = Find(a);
           42  +   b = Find(b);
           43  +   if( a != b )
           44  +   {
           45  +    if( sz[a] >= sz[b] ) swap(a, b);
           46  +    uf[a] = b;
           47  +    sz[b] += sz[a];
           48  +    --nc;
           49  +   }
           50  +   return (a!=b);
           51  +  }
           52  +};
           53  +
           54  +class MagicBoard { public:
           55  + string ableToUnlock(vector <string> board)
           56  + {
           57  +  const int H = board.size();
           58  +  const int W = board[0].size();
           59  +  vector<int> deg(H+W);
           60  +  UnionFind uf(H*W);
           61  +
           62  +  int num = 0;
           63  +  for(int y=0; y<H; ++y)
           64  +  for(int x=0; x<W; ++x)
           65  +   if( board[y][x]=='#' ) {
           66  +    deg[y]++;
           67  +    deg[H+x]++;
           68  +    num++;
           69  +    for(int yy=0; yy<H; ++yy)
           70  +     if( board[yy][x]=='#' )
           71  +      uf.Union(y*W+x, yy*W+x);
           72  +    for(int xx=0; xx<W; ++xx)
           73  +     if( board[y][xx]=='#' )
           74  +      uf.Union(y*W+x, y*W+xx);
           75  +   }
           76  +  int odd_y = 0, odd_x = 0;
           77  +  for(int y=0; y<H; ++y)
           78  +   odd_y += (deg[y]%2==1);
           79  +  for(int x=0; x<W; ++x)
           80  +   odd_x += (deg[H+x]%2==1);
           81  +  return (uf.size()==H*W-num+1 && odd_y+odd_x<=2 && odd_y<2 ? "YES" : "NO");
           82  + }
           83  +};
           84  +
           85  +// BEGIN CUT HERE
           86  +#include <ctime>
           87  +double start_time; string timer()
           88  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           89  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           90  + { os << "{ ";
           91  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           92  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           93  +void verify_case(const string& Expected, const string& Received) {
           94  + bool ok = (Expected == Received);
           95  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           96  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           97  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           98  +#define END  verify_case(_, MagicBoard().ableToUnlock(board));}
           99  +int main(){
          100  +
          101  +CASE(0)
          102  + string board_[] = {"##",
          103  + ".#"};
          104  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          105  + string _ = "YES";
          106  +END
          107  +CASE(1)
          108  + string board_[] = {"#.",
          109  + ".#"};
          110  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          111  + string _ = "NO";
          112  +END
          113  +CASE(2)
          114  + string board_[] = {"##",
          115  + "##",
          116  + "##"};
          117  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          118  + string _ = "YES";
          119  +END
          120  +CASE(3)
          121  + string board_[] = {"###",
          122  + "###",
          123  + "###"};
          124  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          125  + string _ = "NO";
          126  +END
          127  +CASE(4)
          128  + string board_[] = {"###",
          129  + "..#",
          130  + "###",
          131  + "#..",
          132  + "###"};
          133  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          134  + string _ = "NO";
          135  +END
          136  +CASE(5)
          137  + string board_[] = {"................",
          138  + ".######..######.",
          139  + ".######..######.",
          140  + ".##......##..##.",
          141  + ".##......##..##.",
          142  + ".######..######.",
          143  + ".######..######.",
          144  + ".....##..##..##.",
          145  + ".....##..##..##.",
          146  + ".######..######.",
          147  + ".######..######.",
          148  + "................"};
          149  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          150  + string _ = "YES";
          151  +END
          152  +CASE(6)
          153  + string board_[] = {"#"};
          154  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          155  + string _ = "YES";
          156  +END
          157  +CASE(7)
          158  +string board_[] = {".#"};
          159  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          160  +   string _ = "YES";
          161  +END
          162  +CASE(8)
          163  +string board_[] = {
          164  + "#################################################",
          165  + "#################################################",
          166  + "#################################################",
          167  + "#################################################",
          168  + "#################################################",
          169  + "#################################################",
          170  + "#################################################",
          171  + "#################################################",
          172  + "#################################################",
          173  + "#################################################",
          174  + "#################################################",
          175  + "#################################################",
          176  + "#################################################",
          177  + "#################################################",
          178  + "#################################################",
          179  + "#################################################",
          180  + "#################################################",
          181  + "#################################################",
          182  + "#################################################",
          183  + "#################################################",
          184  + "#################################################",
          185  + "#################################################",
          186  + "#################################################",
          187  + "#################################################",
          188  + "#################################################",
          189  + "#################################################",
          190  + "#################################################",
          191  + "#################################################",
          192  + "#################################################",
          193  + "#################################################",
          194  + "#################################################",
          195  + "#################################################",
          196  + "#################################################",
          197  + "#################################################",
          198  + "#################################################",
          199  + "#################################################",
          200  + "#################################################",
          201  + "#################################################",
          202  + "#################################################",
          203  + "#################################################",
          204  + "#################################################",
          205  + "#################################################",
          206  + "#################################################",
          207  + "#################################################",
          208  + "#################################################",
          209  + "#################################################",
          210  + "#################################################",
          211  + "#################################################",
          212  + "#################################################",
          213  + "#################################################",
          214  +};
          215  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          216  + string _ = "???";
          217  +END
          218  +
          219  +}
          220  +// END CUT HERE