Overview
| SHA1 Hash: | c9008fc6676a002f549bec8c719d746b57276c46 |
|---|---|
| Date: | 2012-08-08 11:48:59 |
| User: | kinaba |
| Comment: | 549 1C done. |
| 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
Deleted SRM/549-U/1A.cpp version [9fc4b0d6d011b0bd]
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 using namespace std; < 18 typedef long long LL; < 19 typedef long double LD; < 20 typedef complex<LD> CMP; < 21 < 22 typedef int vert; < 23 typedef vert edge; < 24 typedef vector<edge> edges; < 25 typedef vector<edges> graph; < 26 < 27 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) < 28 { < 29 for(int i=0; i<G[v].size(); ++i) { < 30 vert u = G[v][i]; < 31 if( visited[u] ) continue; < 32 visited[u] = true; < 33 < 34 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) < 35 { matchTo[v]=u, matchTo[u]=v; return true; } < 36 } < 37 return false; < 38 } < 39 < 40 template<int NV> < 41 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right < 42 { < 43 vector<vert> matchTo(G.size(), -1); < 44 int ans = 0; < 45 for(vert v=0; v<L; ++v) { < 46 bool visited[NV] = {}; < 47 if( augment(G, v, matchTo, visited) ) < 48 ++ans; < 49 } < 50 return ans; < 51 } < 52 < 53 class PointyWizardHats { public: < 54 int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <i < 55 { < 56 int L = topHeight.size(); < 57 int R = bottomHeight.size(); < 58 graph G(L+R); < 59 for(int i=0; i<L; ++i) < 60 for(int k=0; k<R; ++k) < 61 if( ok(topHeight[i], topRadius[i], bottomHeight[ < 62 G[i].push_back(L+k); < 63 return biMatch<100>(G, L); < 64 } < 65 < 66 bool ok(int th, int tr, int bh, int br) < 67 { < 68 if( th*br > bh*tr ) { < 69 return br > tr; < 70 } < 71 return false; < 72 } < 73 }; < 74 < 75 // BEGIN CUT HERE < 76 #include <ctime> < 77 double start_time; string timer() < 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 80 { os << "{ "; < 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 83 void verify_case(const int& Expected, const int& Received) { < 84 bool ok = (Expected == Received); < 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 88 #define END verify_case(_, PointyWizardHats().getNumHats(topHeight, topRadi < 89 int main(){ < 90 < 91 CASE(0) < 92 int topHeight_[] = {30}; < 93 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 94 int topRadius_[] = {3}; < 95 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 96 int bottomHeight_[] = {3}; < 97 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 98 int bottomRadius_[] = {30}; < 99 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 100 int _ = 1; < 101 END < 102 CASE(1) < 103 int topHeight_[] = {4,4}; < 104 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 105 int topRadius_[] = {4,3}; < 106 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 107 int bottomHeight_[] = {5,12}; < 108 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 109 int bottomRadius_[] = {5,4}; < 110 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 111 int _ = 1; < 112 END < 113 CASE(2) < 114 int topHeight_[] = {3}; < 115 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 116 int topRadius_[] = {3}; < 117 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 118 int bottomHeight_[] = {1,1}; < 119 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 120 int bottomRadius_[] = {2,4}; < 121 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 122 int _ = 1; < 123 END < 124 CASE(3) < 125 int topHeight_[] = {10,10}; < 126 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 127 int topRadius_[] = {2,5}; < 128 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 129 int bottomHeight_[] = {2,9}; < 130 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 131 int bottomRadius_[] = {3,6}; < 132 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 133 int _ = 2; < 134 END < 135 CASE(4) < 136 int topHeight_[] = {3,4,5}; < 137 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 138 int topRadius_[] = {5,4,3}; < 139 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 140 int bottomHeight_[] = {3,4,5}; < 141 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 142 int bottomRadius_[] = {3,8,5}; < 143 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 144 int _ = 2; < 145 END < 146 CASE(5) < 147 int topHeight_[] = {1,2,3,4,5}; < 148 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 149 int topRadius_[] = {2,3,4,5,6}; < 150 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 151 int bottomHeight_[] = {2,3,4,5,6}; < 152 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 153 int bottomRadius_[] = {1,2,3,4,5}; < 154 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 155 int _ = 0; < 156 END < 157 CASE(6) < 158 int topHeight_[] = {123,214,232,323,342,343}; < 159 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 160 int topRadius_[] = {123,123,232,123,323,434}; < 161 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 162 int bottomHeight_[] = {545,322,123,545,777,999}; < 163 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 164 int bottomRadius_[] = {323,443,123,656,767,888}; < 165 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 166 int _ = 5; < 167 END < 168 CASE(7) < 169 int topHeight_[] = {999,999,999,10000,10000,10000}; < 170 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 171 int topRadius_[] = {10000,10000,10000,1,2,3}; < 172 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 173 int bottomHeight_[] = {2324,2323,234,5454,323,232}; < 174 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 175 int bottomRadius_[] = {1,2,3222,434,5454,23}; < 176 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 177 int _ = 3; < 178 END < 179 /* < 180 CASE(8) < 181 int topHeight_[] = ; < 182 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 183 int topRadius_[] = ; < 184 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 185 int bottomHeight_[] = ; < 186 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 187 int bottomRadius_[] = ; < 188 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 189 int _ = ; < 190 END < 191 CASE(9) < 192 int topHeight_[] = ; < 193 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo < 194 int topRadius_[] = ; < 195 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo < 196 int bottomHeight_[] = ; < 197 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe < 198 int bottomRadius_[] = ; < 199 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa < 200 int _ = ; < 201 END < 202 */ < 203 } < 204 // END CUT HERE <
Deleted SRM/549-U/1B.cpp version [124cec5a706621e0]
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 using namespace std; < 18 typedef long long LL; < 19 typedef long double LD; < 20 typedef complex<LD> CMP; < 21 < 22 class MagicalHats { public: < 23 int NC, NH, H, W, NG; < 24 vector<int> gain; < 25 vector< pair<int,int> > hats; < 26 vector<int> tate_base, yoko_base; < 27 < 28 int findMaximumReward(vector <string> board, vector <int> coins, int num < 29 { < 30 NC = coins.size(); < 31 sort(coins.begin(), coins.end()); < 32 gain.assign(NC+1, 0); < 33 partial_sum(coins.begin(), coins.end(), gain.begin()+1); < 34 < 35 H = board.size(); < 36 W = board[0].size(); < 37 hats.clear(); < 38 tate_base.resize(W); < 39 yoko_base.resize(H); < 40 for(int y=0; y<H; ++y) < 41 for(int x=0; x<W; ++x) < 42 if(board[y][x] == 'H') { < 43 hats.push_back( make_pair(y,x) ); < 44 tate_base[x]++; < 45 yoko_base[y]++; < 46 } < 47 NH = hats.size(); < 48 NG = numGuesses; < 49 < 50 int m = 0; < 51 for(int i=0; i<NH; ++i) < 52 m = m*3 + 2; < 53 p_memo.resize(m+1); < 54 p_memo_set.resize(m+1); < 55 b_memo.resize(m+1); < 56 b_memo_set.resize(m+1); < 57 return is_possible(m) ? gain[best_num(m, NG)] : -1; < 58 } < 59 < 60 vector<bool> p_memo; < 61 vector<bool> p_memo_set; < 62 bool is_possible(int state) < 63 { < 64 if(p_memo_set[state]) < 65 return p_memo[state]; < 66 p_memo_set[state] = true; < 67 < 68 vector<int> yoko = yoko_base, tate = tate_base, next; < 69 int cnt = 0; < 70 for(int i=0,m=1; i<NH; ++i,m*=3) < 71 { < 72 int v = (state/m)%3; < 73 if( v == 1 ) { < 74 int y = hats[i].first; < 75 int x = hats[i].second; < 76 yoko[y]++; < 77 tate[x]++; < 78 ++cnt; < 79 } else if( v == 2 ) { < 80 next.push_back(m); < 81 } < 82 } < 83 if( next.empty() ) < 84 { < 85 if( cnt != NC ) < 86 return false; < 87 for(int y=0; y<yoko.size(); ++y) < 88 if(yoko[y]%2 != 0) < 89 return p_memo[state] = false; < 90 for(int x=0; x<tate.size(); ++x) < 91 if(tate[x]%2 != 0) < 92 return p_memo[state] = false; < 93 return p_memo[state] = true; < 94 } < 95 else < 96 { < 97 int m = next[0]; < 98 int s[] = {state-2*m, state-m}; < 99 return p_memo[state] = ( is_possible(s[0]) || is_possibl < 100 } < 101 } < 102 < 103 vector<char> b_memo; < 104 vector<bool> b_memo_set; < 105 char best_num(int state, int guess) < 106 { < 107 if( guess==0 ) < 108 return 0; < 109 if(b_memo_set[state]) < 110 return b_memo[state]; < 111 b_memo_set[state] = true; < 112 < 113 char best = 0; < 114 for(int i=0,m=1; i<NH; ++i,m*=3) < 115 { < 116 int v = (state/m)%3; < 117 if( v == 2 ) < 118 { < 119 int s[] = {state-2*m, state-m}; < 120 char score = 13; < 121 if( is_possible(s[0]) ) < 122 score = min(score, best_num(s[0], guess- < 123 if( is_possible(s[1]) ) < 124 score = min<char>(score, best_num(s[1], < 125 best = max(best, score); < 126 } < 127 } < 128 return b_memo[state] = best; < 129 } < 130 }; < 131 < 132 // BEGIN CUT HERE < 133 #include <ctime> < 134 double start_time; string timer() < 135 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 136 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 137 { os << "{ "; < 138 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 139 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 140 void verify_case(const int& Expected, const int& Received) { < 141 bool ok = (Expected == Received); < 142 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 143 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 144 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 145 #define END verify_case(_, MagicalHats().findMaximumReward(board, coins, nu < 146 int main(){ < 147 < 148 CASE(0) < 149 string board_[] = {"H"}; < 150 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 151 int coins_[] = {1}; < 152 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 153 int numGuesses = 1; < 154 int _ = 1; < 155 END < 156 CASE(1) < 157 string board_[] = {"HHH", < 158 "H.H", < 159 "HH."}; < 160 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 161 int coins_[] = {9}; < 162 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 163 int numGuesses = 1; < 164 int _ = 9; < 165 END < 166 CASE(2) < 167 string board_[] = {"HH", < 168 "HH"}; < 169 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 170 int coins_[] = {1,2,3,4}; < 171 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 172 int numGuesses = 3; < 173 int _ = 6; < 174 END < 175 CASE(3) < 176 string board_[] = {"HHH", < 177 "HHH", < 178 "H.H"}; < 179 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 180 int coins_[] = {13,13,13,13}; < 181 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 182 int numGuesses = 2; < 183 int _ = 13; < 184 END < 185 CASE(4) < 186 string board_[] = {"HHH", < 187 "HHH", < 188 "H.H"}; < 189 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 190 int coins_[] = {13,13,13,13}; < 191 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 192 int numGuesses = 3; < 193 int _ = 26; < 194 END < 195 CASE(5) < 196 string board_[] = {"H.H.", < 197 ".H.H", < 198 "H.H."}; < 199 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 200 int coins_[] = {17}; < 201 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 202 int numGuesses = 6; < 203 int _ = -1; < 204 END < 205 CASE(6) < 206 string board_[] = {"HHH..........", < 207 "H.H..........", < 208 "HHH..........", < 209 "H.H..........", < 210 "HHH.........." < 211 ".............", < 212 ".............", < 213 ".............", < 214 ".............", < 215 ".............", < 216 ".............", < 217 ".............", < 218 ".............", < 219 }; < 220 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 221 int coins_[] = {33,337,1007,2403,5601,6003,9999}; < 222 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 223 int numGuesses = 5; < 224 int _ = 1377; < 225 END < 226 CASE(7) < 227 string board_[] = {".............", < 228 ".............", < 229 ".............", < 230 ".............", < 231 ".............", < 232 ".............", < 233 ".....H.H.....", < 234 "......H......", < 235 ".....H.H.....", < 236 ".............", < 237 ".............", < 238 ".............", < 239 "............."}; < 240 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 241 int coins_[] = {22}; < 242 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 243 int numGuesses = 3; < 244 int _ = 22; < 245 END < 246 /* < 247 CASE(8) < 248 string board_[] = ; < 249 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 250 int coins_[] = ; < 251 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 252 int numGuesses = ; < 253 int _ = ; < 254 END < 255 CASE(9) < 256 string board_[] = ; < 257 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); < 258 int coins_[] = ; < 259 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); < 260 int numGuesses = ; < 261 int _ = ; < 262 END < 263 */ < 264 } < 265 // END CUT HERE <
Name change from from SRM/549-U/1A.cpp to SRM/549/1A.cpp.
Name change from from SRM/549-U/1B.cpp to SRM/549/1B.cpp.
Added SRM/549/1C.cpp version [fede1c18ad40c4e3]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 template<typename Vert, typename Flow, int NV=16> > 23 class MaxFlow > 24 { > 25 vector<int> G[NV]; > 26 Flow F[NV][NV]; > 27 > 28 public: > 29 void addEdge( Vert s, Vert t, Flow f ) > 30 { > 31 G[s].push_back(t); > 32 G[t].push_back(s); > 33 F[s][t] = f; > 34 F[t][s] = 0; > 35 } > 36 > 37 Flow calc( Vert S, Vert D ) > 38 { > 39 for( Flow total=0 ;; ) { > 40 // Do BFS and compute the level for each node. > 41 int LV[NV] = {0}; > 42 vector<int> Q(1, S); > 43 for(int lv=1; !Q.empty(); ++lv) { > 44 vector<int> Q2; > 45 for(size_t i=0; i!=Q.size(); ++i) { > 46 const vector<int>& ne = G[Q[i]]; > 47 for(size_t j=0; j!=ne.size(); ++j) > 48 if( F[Q[i]][ne[j]] && !LV[ne[j]] > 49 LV[ne[j]]=lv, Q2.push_ba > 50 } > 51 Q.swap(Q2); > 52 } > 53 > 54 // Destination is now unreachable. Done. > 55 if( !LV[D] ) > 56 return total; > 57 > 58 // Iterating DFS. > 59 bool blocked[NV] = {}; > 60 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 61 } > 62 } > 63 > 64 private: > 65 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 66 { > 67 Flow flow_out = 0; > 68 for(size_t i=0; i!=G[v].size(); ++i) { > 69 int u = G[v][i]; > 70 if( LV[v]+1==LV[u] && F[v][u] ) { > 71 Flow f = min(flow_in-flow_out, F[v][u]); > 72 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 73 F[v][u] -= f; > 74 F[u][v] += f; > 75 flow_out += f; > 76 if( flow_in == flow_out ) return flow_ou > 77 } > 78 } > 79 } > 80 blocked[v] = (flow_out==0); > 81 return flow_out; > 82 } > 83 }; > 84 > 85 class CosmicBlocks { public: > 86 vector<int> blockTypes; > 87 int N, minWays, maxWays; > 88 > 89 int getNumOrders(vector <int> blockTypes_, int minWays_, int maxWays_) > 90 { > 91 N = blockTypes_.size(); > 92 blockTypes = blockTypes_; > 93 minWays = minWays_; > 94 maxWays = maxWays_; > 95 return try_all_latitude(); > 96 } > 97 > 98 int try_all_latitude() > 99 { > 100 vector<int> lat; > 101 return rec_assign_latitude(&lat, (1<<N)-1, 0x7fffffff); > 102 } > 103 > 104 int rec_assign_latitude(vector<int>* lat, int mask, int prev_lat_blocks) > 105 { > 106 if( mask == 0 ) > 107 return try_all_touching_releation(*lat); > 108 > 109 int total = 0; > 110 for(int m=1; m<=mask; ++m) if( (m&mask)==m ) { > 111 int sum = 0; > 112 for(int i=0; (1<<i)<=m; ++i) if(1<<i & m) > 113 sum+=blockTypes[i]; > 114 if( prev_lat_blocks >= sum ) { > 115 lat->push_back(m); > 116 total += rec_assign_latitude(lat, mask&~m, sum); > 117 lat->pop_back(); > 118 } > 119 } > 120 return total; > 121 } > 122 > 123 int try_all_touching_releation(const vector<int>& lat) > 124 { > 125 int total = 0; > 126 > 127 vector<int> fst = elements(lat[0]); > 128 vector< pair<int,int> > adj = adjacent_blocks(lat); > 129 for(int m=0; m<(1<<adj.size()); ++m) > 130 { > 131 vector< vector<int> > up(N); > 132 up.push_back(fst); > 133 for(int i=0; (1<<i)<=m; ++i) if(1<<i & m) > 134 up[adj[i].first].push_back(adj[i].second); > 135 > 136 if( !possible(up) ) > 137 continue; > 138 int ways = calc_ways(up); > 139 if( minWays<=ways && ways<=maxWays ) > 140 ++total; > 141 } > 142 return total; > 143 } > 144 > 145 vector<int> elements(int mask) > 146 { > 147 vector<int> result; > 148 for(int i=0; (1<<i)<=mask; ++i) if(1<<i & mask) > 149 result.push_back(i); > 150 return result; > 151 } > 152 > 153 vector< pair<int,int> > adjacent_blocks(const vector<int>& lat) > 154 { > 155 vector< pair<int,int> > result; > 156 for(int i=1; i<lat.size(); ++i) > 157 for(int a=0; (1<<a)<=lat[i-1]; ++a) if(1<<a & lat[i-1]) > 158 for(int b=0; (1<<b)<=lat[i]; ++b) if(1<<b & lat[i]) > 159 result.push_back(make_pair(a,b)); > 160 return result; > 161 } > 162 > 163 int calc_ways(const vector< vector<int> >& up) > 164 { > 165 vector<int> governed(N); > 166 for(int i=0; i<up.size(); ++i) > 167 for(int k=0; k<up[i].size(); ++k) > 168 governed[up[i][k]] ++; > 169 > 170 // trivial check 2 > 171 for(int i=0; i<governed.size(); ++i) > 172 if(governed[i] == 0) > 173 return 0; > 174 > 175 vector<int> memo(1<<N, -1); > 176 return calc_ways_rec(N, (1<<N)-1, up, governed, memo); > 177 } > 178 > 179 int calc_ways_rec(int i, int mask, const vector< vector<int> >& up, vect > 180 vector<int>& memo) > 181 { > 182 if(mask == 0) > 183 return 1; > 184 if(memo[mask] != -1) > 185 return memo[mask]; > 186 > 187 int sum = 0; > 188 > 189 for(int k=0; k<up[i].size(); ++k) governed[up[i][k]]--; > 190 { > 191 for(int k=0; k<governed.size(); ++k) > 192 if(!governed[k] && (mask & 1<<k)) > 193 sum += calc_ways_rec(k, mask &~ (1<<k), > 194 } > 195 for(int k=0; k<up[i].size(); ++k) governed[up[i][k]]++; > 196 > 197 return memo[mask] = sum; > 198 } > 199 > 200 bool possible(const vector< vector<int> >& up) > 201 { > 202 static const int INF = 0x3fffffff; > 203 > 204 int total = accumulate(blockTypes.begin(), blockTypes.end(), 0); > 205 > 206 MaxFlow<int, int> mf; > 207 vector<int> out = blockTypes, in = blockTypes; > 208 for(int v=0; v<=N; ++v) { > 209 for(int i=0; i<up[v].size(); ++i) { > 210 int u = up[v][i]; > 211 mf.addEdge(v, N+1+u, INF); > 212 if(v<N) {in[v] -= 1; if(in[v]<0) return false; } > 213 out[u] -= 1; if(out[u]<0) return false; > 214 total -= 1; > 215 } > 216 } > 217 for(int v=0; v<=N; ++v) > 218 if(v == N) { > 219 mf.addEdge(N+1+N, v, INF); > 220 } else { > 221 mf.addEdge(N+1+N, v, in[v]); > 222 mf.addEdge(N+1+v, N+1+N+1, out[v]); > 223 } > 224 return mf.calc(N+1+N, N+1+N+1) == total; > 225 } > 226 }; > 227 > 228 // BEGIN CUT HERE > 229 #include <ctime> > 230 double start_time; string timer() > 231 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 232 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 233 { os << "{ "; > 234 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 235 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 236 void verify_case(const int& Expected, const int& Received) { > 237 bool ok = (Expected == Received); > 238 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 239 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 240 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 241 #define END verify_case(_, CosmicBlocks().getNumOrders(blockTypes, minWays, > 242 int main(){ > 243 > 244 CASE(0) > 245 int blockTypes_[] = {2,2,2}; > 246 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 247 int minWays = 1; > 248 int maxWays = 1; > 249 int _ = 6; > 250 END > 251 CASE(1) > 252 int blockTypes_[] = {1,1,1,1,1,1}; > 253 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 254 int minWays = 720; > 255 int maxWays = 720; > 256 int _ = 1; > 257 END > 258 CASE(2) > 259 int blockTypes_[] = {2,2}; > 260 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 261 int minWays = 1; > 262 int maxWays = 2; > 263 int _ = 3; > 264 END > 265 CASE(3) > 266 int blockTypes_[] = {1,2}; > 267 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 268 int minWays = 1; > 269 int maxWays = 2; > 270 int _ = 2; > 271 END > 272 CASE(4) > 273 int blockTypes_[] = {1}; > 274 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 275 int minWays = 1; > 276 int maxWays = 1; > 277 int _ = 1; > 278 END > 279 CASE(5) > 280 int blockTypes_[] = {1,2,4,8}; > 281 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 282 int minWays = 5; > 283 int maxWays = 30; > 284 int _ = 27; > 285 END > 286 CASE(6) > 287 int blockTypes_[] = {1,2,3,4,5,6}; > 288 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 289 int minWays = 1; > 290 int maxWays = 720; > 291 int _ = 4445; > 292 END > 293 CASE(7) > 294 int blockTypes_[] = {7500,1000,7500,1000,7500}; > 295 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 296 int minWays = 8; > 297 int maxWays = 88; > 298 int _ = 448; > 299 END > 300 /* > 301 CASE(8) > 302 int blockTypes_[] = ; > 303 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 304 int minWays = ; > 305 int maxWays = ; > 306 int _ = ; > 307 END > 308 CASE(9) > 309 int blockTypes_[] = ; > 310 vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/s > 311 int minWays = ; > 312 int maxWays = ; > 313 int _ = ; > 314 END > 315 */ > 316 } > 317 // END CUT HERE