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

Added SRM/530-U/1A.cpp version [18ebe86cb67a2579]

            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 GogoXCake { public:
           29  + string solve(vector <string> cake, vector <string> cutter)
           30  + {
           31  +  const int theX = cutter[0].find('.');
           32  +
           33  +  for(int y=0; y<cake.size(); ++y)
           34  +  for(int x=0; x<cake[y].size(); ++x) {
           35  +   if( cake[y][x] == '.' ) {
           36  +    if( !place(cake, y, x-theX, cutter) )
           37  +     return "NO";
           38  +   }
           39  +  }
           40  +  return "YES";
           41  + }
           42  +
           43  + bool place(vector <string>& cake, int Y, int X, const vector <string>& cutter)
           44  + {
           45  +  for(int y=0; y<cutter.size(); ++y)
           46  +  for(int x=0; x<cutter[y].size(); ++x)
           47  +  {
           48  +   int yy = Y+y, xx = X+x;
           49  +   if( yy<0 || cake.size()<=yy || xx<0 || cake[0].size()<=xx )
           50  +    return false;
           51  +   if( cutter[y][x]=='.' ) {
           52  +    if( cake[yy][xx]=='X' )
           53  +     return false;
           54  +    cake[yy][xx] = 'X';
           55  +   }
           56  +  }
           57  +  return true;
           58  + }
           59  +};
           60  +
           61  +// BEGIN CUT HERE
           62  +#include <ctime>
           63  +double start_time; string timer()
           64  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           65  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           66  + { os << "{ ";
           67  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           68  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           69  +void verify_case(const string& Expected, const string& Received) {
           70  + bool ok = (Expected == Received);
           71  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           72  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           73  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           74  +#define END  verify_case(_, GogoXCake().solve(cake, cutter));}
           75  +int main(){
           76  +
           77  +CASE(0)
           78  + string cake_[] = {"X.X"
           79  +,"..."
           80  +,"..."
           81  +,"X.X"};
           82  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
           83  + string cutter_[] = {".X"
           84  +,".."
           85  +,"X."};
           86  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
           87  + string _ = "YES";
           88  +END
           89  +CASE(1)
           90  + string cake_[] = {"..XX"
           91  +,"...X"
           92  +,"X..."
           93  +,"XX.."};
           94  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
           95  + string cutter_[] = {".."
           96  +,".."};
           97  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
           98  + string _ = "NO";
           99  +END
          100  +CASE(2)
          101  + string cake_[] = {"...X..."};
          102  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          103  + string cutter_[] = {"..."};
          104  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          105  + string _ = "YES";
          106  +END
          107  +CASE(3)
          108  + string cake_[] = {".X."
          109  +,"X.X"
          110  +,".X."};
          111  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          112  + string cutter_[] = {"."};
          113  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          114  + string _ = "YES";
          115  +END
          116  +CASE(4)
          117  + string cake_[] = {"XXXXXXX"
          118  +,"X.....X"
          119  +,"X.....X"
          120  +,"X.....X"
          121  +,"XXXXXXX"};
          122  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          123  + string cutter_[] = {".X."
          124  +,"XXX"
          125  +,".X."};
          126  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          127  + string _ = "NO";
          128  +END
          129  +CASE(5)
          130  + string cake_[] = {".."
          131  +,"X."
          132  +,".X"};
          133  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          134  + string cutter_[] = {".."
          135  +,".X"
          136  +,"X."};
          137  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          138  + string _ = "NO";
          139  +END
          140  +CASE(6)
          141  + string cake_[] = {"X.."
          142  +,".XX"
          143  +,".XX"};
          144  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          145  + string cutter_[] = {".XX"
          146  +,".XX"
          147  +,"X.."};
          148  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          149  + string _ = "NO";
          150  +END
          151  +/*
          152  +CASE(7)
          153  + string cake_[] = ;
          154  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          155  + string cutter_[] = ;
          156  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          157  + string _ = ;
          158  +END
          159  +CASE(8)
          160  + string cake_[] = ;
          161  +   vector <string> cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_));
          162  + string cutter_[] = ;
          163  +   vector <string> cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_));
          164  + string _ = ;
          165  +END
          166  +*/
          167  +}
          168  +// END CUT HERE

Added SRM/530-U/1B2C.cpp version [ab7535f57aeca737]

            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 GogoXReimuHakurai { public:
           29  + int solve(vector <string> choices)
           30  + {
           31  +  set<int> fromSrc;
           32  +  {
           33  +   queue<int> q;
           34  +   q.push(0);
           35  +   fromSrc.insert(0);
           36  +   while( !q.empty() ) {
           37  +    int v = q.front();
           38  +    q.pop();
           39  +    for(int u=0; u<choices[v].size(); ++u)
           40  +     if( choices[v][u] == 'Y' && !fromSrc.count(u) )
           41  +      q.push(u), fromSrc.insert(u);
           42  +   }
           43  +  }
           44  +  set<int> toDest;
           45  +  {
           46  +   queue<int> q;
           47  +   q.push(choices.size()-1);
           48  +   toDest.insert(choices.size()-1);
           49  +   while( !q.empty() ) {
           50  +    int v = q.front();
           51  +    q.pop();
           52  +    for(int u=0; u<choices[v].size(); ++u)
           53  +     if( choices[u][v] == 'Y' && !toDest.count(u) )
           54  +      q.push(u), toDest.insert(u);
           55  +   }
           56  +  }
           57  +  set<int> valid;
           58  +  set_intersection(fromSrc.begin(), fromSrc.end(),
           59  +                   toDest.begin(), toDest.end(),
           60  +       inserter(valid, valid.begin()));
           61  +  int N = valid.size();
           62  +  int E = 0;
           63  +  for(int v=0; v<choices.size(); ++v) if(valid.count(v))
           64  +  for(int u=0; u<choices.size(); ++u) if(v!=u && valid.count(u))
           65  +   if( choices[v][u]=='Y' )
           66  +    ++E;
           67  +  return N ? E - (N-2) : 0;
           68  + }
           69  +};
           70  +
           71  +// BEGIN CUT HERE
           72  +#include <ctime>
           73  +double start_time; string timer()
           74  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           75  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           76  + { os << "{ ";
           77  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           78  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           79  +void verify_case(const int& Expected, const int& Received) {
           80  + bool ok = (Expected == Received);
           81  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           82  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           83  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           84  +#define END  verify_case(_, GogoXReimuHakurai().solve(choices));}
           85  +int main(){
           86  +
           87  +CASE(0)
           88  + string choices_[] = {
           89  +"NYY",
           90  +"NNY",
           91  +"NNN"};
           92  +   vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_));
           93  + int _ = 2;
           94  +END
           95  +CASE(1)
           96  + string choices_[] = {
           97  +"NYNY",
           98  +"NNYY",
           99  +"NNNY",
          100  +"NNNN"};
          101  +   vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_));
          102  + int _ = 3;
          103  +END
          104  +CASE(2)
          105  + string choices_[] = {"NNY"
          106  +,"NNY"
          107  +,"NNN"};
          108  +   vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_));
          109  + int _ = 1;
          110  +END
          111  +CASE(3)
          112  + string choices_[] = {"NN"
          113  +,"NN"};
          114  +   vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_));
          115  + int _ = 0;
          116  +END
          117  +/*
          118  +CASE(4)
          119  + string choices_[] = ;
          120  +   vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_));
          121  + int _ = ;
          122  +END
          123  +CASE(5)
          124  + string choices_[] = ;
          125  +   vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_));
          126  + int _ = ;
          127  +END
          128  +*/
          129  +}
          130  +// END CUT HERE