Overview
| SHA1 Hash: | e874ae142a68b95c274b2b4d0266e115eacff48b |
|---|---|
| Date: | 2015-07-10 00:52:42 |
| User: | kinaba |
| Comment: | TCO15 2b |
| 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/TCO15-2B/1A.cpp version [f77c6b1cfc679969]
> 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 class Bitwisdom { public: > 23 double expectedActions(vector <int> p) > 24 { > 25 double e = 0; > 26 for(int i=1; i<p.size(); ++i) { > 27 e += (p[i]/100.0) * (100-p[i-1])/100.0 > 28 + (p[i-1]/100.0) * (100-p[i])/100.0; > 29 } > 30 double q = 1.0; > 31 for(int i=0; i<p.size(); ++i) > 32 q *= (p[i]/100.0); > 33 return e + q; > 34 } > 35 }; > 36 > 37 // BEGIN CUT HERE > 38 #include <ctime> > 39 double start_time; string timer() > 40 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 41 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 42 { os << "{ "; > 43 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 44 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 45 void verify_case(const double& Expected, const double& Received) { > 46 bool ok = (abs(Expected - Received) < 1e-9); > 47 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 48 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 49 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 50 #define END verify_case(_, Bitwisdom().expectedActions(p));} > 51 int main(){ > 52 > 53 CASE(0) > 54 int p_[] = {100, 100, 100}; > 55 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 56 double _ = 1.0; > 57 END > 58 CASE(1) > 59 int p_[] = {50, 50}; > 60 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 61 double _ = 0.75; > 62 END > 63 CASE(2) > 64 int p_[] = {0, 40, 50, 60}; > 65 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 66 double _ = 1.4; > 67 END > 68 CASE(3) > 69 int p_[] = {37, 63, 23, 94, 12}; > 70 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 71 double _ = 2.6820475464; > 72 END > 73 /* > 74 CASE(4) > 75 int p_[] = ; > 76 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 77 double _ = ; > 78 END > 79 CASE(5) > 80 int p_[] = ; > 81 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 82 double _ = ; > 83 END > 84 */ > 85 } > 86 // END CUT HERE
Added SRM/TCO15-2B/1B.cpp version [1948580a37893b4c]
> 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 class Balance { public: > 23 string canTransform(vector <string> initial, vector <string> target) > 24 { > 25 auto ti = gen_tree(initial); > 26 auto tt = gen_tree(target); > 27 return tree_eq(ti, tt) ? "Possible" : "Impossible"; > 28 } > 29 > 30 vector<vector<int>> gen_tree(vector<string> s) { > 31 s.push_back(string(s[0].size(), '#')); > 32 s.insert(s.begin(), string(s[0].size(), '#')); > 33 for(auto& si: s) > 34 si = '#'+si+'#'; > 35 > 36 const int H = s.size(), W = s[0].size(); > 37 const int NOTYET = 0x7fffffff; > 38 > 39 vector<vector<int>> tree; > 40 vector<vector<int>> parent_cand(H, vector<int>(W, -1)); > 41 vector<vector<int>> color(H, vector<int>(W, NOTYET)); > 42 for(int y=0; y<H; ++y) > 43 for(int x=0; x<W; ++x) > 44 if(color[y][x]==NOTYET) { > 45 const char ME = s[y][x]; > 46 int newId = tree.size(); > 47 tree.resize(newId+1); > 48 > 49 // BFS > 50 set<int> tonari; > 51 > 52 queue<pair<int,int>> Q; > 53 color[y][x] = newId; > 54 Q.emplace(y, x); > 55 while(!Q.empty()) { > 56 int yy = Q.front().first; > 57 int xx = Q.front().second; > 58 Q.pop(); > 59 > 60 int dx[] = {-1,+1,0,0}; > 61 int dy[] = {0,0,-1,+1}; > 62 for(int d=0; d<4; ++d) { > 63 int y2 = yy+dy[d]; > 64 int x2 = xx+dx[d]; > 65 if(0<=x2&&x2<W&&0<=y2&&y2<H) { > 66 if(s[y2][x2]==ME&&color[y2][x2]= > 67 color[y2][x2] = newId; > 68 Q.emplace(y2, x2); > 69 } > 70 if(s[y2][x2]!=ME&&color[y2][x2]! > 71 tonari.insert(color[y2][ > 72 } > 73 } > 74 } > 75 } > 76 if(tonari.size() == 1) > 77 tree[*tonari.begin()].push_back(newId); > 78 } > 79 return tree; > 80 } > 81 > 82 map<vector<int>, int> hashId; > 83 bool tree_eq(const vector<vector<int>>& a, const vector<vector<int>>& b) > 84 { > 85 return hash(a,0) == hash(b,0); > 86 } > 87 > 88 int hash(const vector<vector<int>>& a, int r) > 89 { > 90 vector<int> ch; > 91 for(int v: a[r]) > 92 ch.push_back(hash(a, v)); > 93 sort(ch.begin(), ch.end()); > 94 if(hashId.count(ch)) > 95 return hashId[ch]; > 96 int v = hashId.size(); > 97 return hashId[ch] = v; > 98 } > 99 }; > 100 > 101 // BEGIN CUT HERE > 102 #include <ctime> > 103 double start_time; string timer() > 104 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 105 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 106 { os << "{ "; > 107 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 108 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 109 void verify_case(const string& Expected, const string& Received) { > 110 bool ok = (Expected == Received); > 111 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 113 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 114 #define END verify_case(_, Balance().canTransform(initial, target));} > 115 int main(){ > 116 > 117 CASE(0) > 118 string initial_[] = {"#"}; > 119 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 120 string target_[] = {"."}; > 121 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 122 string _ = "Impossible"; > 123 END > 124 CASE(1) > 125 string initial_[] = {"..", > 126 ".."}; > 127 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 128 string target_[] = {".#", > 129 "##"}; > 130 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 131 string _ = "Possible"; > 132 END > 133 CASE(2) > 134 string initial_[] = {"...", > 135 ".#.", > 136 "..."}; > 137 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 138 string target_[] = {"###", > 139 "#.#", > 140 "###"}; > 141 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 142 string _ = "Impossible"; > 143 END > 144 CASE(3) > 145 string initial_[] = {".#.#.......", > 146 "####.###...", > 147 ".....####..", > 148 "..##.#.##.#", > 149 ".##..#.##.#", > 150 ".#######...", > 151 ".#....###.#", > 152 ".##.#.#....", > 153 "..#...#...#", > 154 "..#####...#", > 155 "..........."}; > 156 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 157 string target_[] = {"...........", > 158 ".###....#..", > 159 ".#.#..#....", > 160 ".###.......", > 161 ".#####.....", > 162 ".#...#####.", > 163 ".#.#.....#.", > 164 ".#.#####.#.", > 165 ".#.......#.", > 166 ".#########.", > 167 "..........."}; > 168 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 169 string _ = "Impossible"; > 170 END > 171 CASE(4) > 172 string initial_[] = {".....", > 173 ".###.", > 174 ".....", > 175 ".###.", > 176 "....."}; > 177 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 178 string target_[] = {".....", > 179 ".#.#.", > 180 ".#.#.", > 181 ".#.#.", > 182 "....."}; > 183 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 184 string _ = "Possible"; > 185 END > 186 /* > 187 CASE(5) > 188 string initial_[] = ; > 189 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 190 string target_[] = ; > 191 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 192 string _ = ; > 193 END > 194 CASE(6) > 195 string initial_[] = ; > 196 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in > 197 string target_[] = ; > 198 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 199 string _ = ; > 200 END > 201 */ > 202 > 203 } > 204 // END CUT HERE