Overview
| SHA1 Hash: | 15bfca243248d22fccdd98ff17ff0ba83c618550 |
|---|---|
| Date: | 2012-01-31 10:47:34 |
| User: | kinaba |
| Comment: | 530 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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>& c > 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()<=x > 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) > 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 > 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() > 72 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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.cou > 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.coun > 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) > 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 > 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() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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(*ch > 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(*ch > 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(*ch > 109 int _ = 1; > 110 END > 111 CASE(3) > 112 string choices_[] = {"NN" > 113 ,"NN"}; > 114 vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*ch > 115 int _ = 0; > 116 END > 117 /* > 118 CASE(4) > 119 string choices_[] = ; > 120 vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*ch > 121 int _ = ; > 122 END > 123 CASE(5) > 124 string choices_[] = ; > 125 vector <string> choices(choices_, choices_+sizeof(choices_)/sizeof(*ch > 126 int _ = ; > 127 END > 128 */ > 129 } > 130 // END CUT HERE