ADDED SRM/530-U/1A.cpp Index: SRM/530-U/1A.cpp ================================================================== --- SRM/530-U/1A.cpp +++ SRM/530-U/1A.cpp @@ -0,0 +1,168 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +class GogoXCake { public: + string solve(vector cake, vector cutter) + { + const int theX = cutter[0].find('.'); + + for(int y=0; y& cake, int Y, int X, const vector & cutter) + { + for(int y=0; y +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const string& Expected, const string& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, GogoXCake().solve(cake, cutter));} +int main(){ + +CASE(0) + string cake_[] = {"X.X" +,"..." +,"..." +,"X.X"}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {".X" +,".." +,"X."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "YES"; +END +CASE(1) + string cake_[] = {"..XX" +,"...X" +,"X..." +,"XX.."}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {".." +,".."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "NO"; +END +CASE(2) + string cake_[] = {"...X..."}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {"..."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "YES"; +END +CASE(3) + string cake_[] = {".X." +,"X.X" +,".X."}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {"."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "YES"; +END +CASE(4) + string cake_[] = {"XXXXXXX" +,"X.....X" +,"X.....X" +,"X.....X" +,"XXXXXXX"}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {".X." +,"XXX" +,".X."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "NO"; +END +CASE(5) + string cake_[] = {".." +,"X." +,".X"}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {".." +,".X" +,"X."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "NO"; +END +CASE(6) + string cake_[] = {"X.." +,".XX" +,".XX"}; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = {".XX" +,".XX" +,"X.."}; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = "NO"; +END +/* +CASE(7) + string cake_[] = ; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = ; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = ; +END +CASE(8) + string cake_[] = ; + vector cake(cake_, cake_+sizeof(cake_)/sizeof(*cake_)); + string cutter_[] = ; + vector cutter(cutter_, cutter_+sizeof(cutter_)/sizeof(*cutter_)); + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/530-U/1B2C.cpp Index: SRM/530-U/1B2C.cpp ================================================================== --- SRM/530-U/1B2C.cpp +++ SRM/530-U/1B2C.cpp @@ -0,0 +1,130 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +class GogoXReimuHakurai { public: + int solve(vector choices) + { + set fromSrc; + { + queue q; + q.push(0); + fromSrc.insert(0); + while( !q.empty() ) { + int v = q.front(); + q.pop(); + for(int u=0; u toDest; + { + queue q; + q.push(choices.size()-1); + toDest.insert(choices.size()-1); + while( !q.empty() ) { + int v = q.front(); + q.pop(); + for(int u=0; u valid; + set_intersection(fromSrc.begin(), fromSrc.end(), + toDest.begin(), toDest.end(), + inserter(valid, valid.begin())); + int N = valid.size(); + int E = 0; + for(int v=0; v +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, GogoXReimuHakurai().solve(choices));} +int main(){ + +CASE(0) + string choices_[] = { +"NYY", +"NNY", +"NNN"}; + vector choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_)); + int _ = 2; +END +CASE(1) + string choices_[] = { +"NYNY", +"NNYY", +"NNNY", +"NNNN"}; + vector choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_)); + int _ = 3; +END +CASE(2) + string choices_[] = {"NNY" +,"NNY" +,"NNN"}; + vector choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_)); + int _ = 1; +END +CASE(3) + string choices_[] = {"NN" +,"NN"}; + vector choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_)); + int _ = 0; +END +/* +CASE(4) + string choices_[] = ; + vector choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_)); + int _ = ; +END +CASE(5) + string choices_[] = ; + vector choices(choices_, choices_+sizeof(choices_)/sizeof(*choices_)); + int _ = ; +END +*/ +} +// END CUT HERE