Overview
| SHA1 Hash: | 552e57677bf243a2d36a6f7f03d537670e1b1fd8 |
|---|---|
| Date: | 2013-06-14 10:34:31 |
| User: | kinaba |
| Comment: | tco13 r3a |
| 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/TCO13-3A-U/1A.cpp version [2d20777071dc89c6]
> 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<double> CMP; > 21 > 22 int bitcnt(int x) > 23 { > 24 int c = 0; > 25 for(; x; x>>=1) > 26 c += x&1; > 27 return c; > 28 } > 29 > 30 class YetAnotherANDProblem { public: > 31 string test(vector <int> X, int K, vector <int> queries) > 32 { > 33 string s; > 34 for(int i=0; i<queries.size(); ++i) > 35 s += (can(X, K, queries[i]) ? "+" : "-"); > 36 return s; > 37 } > 38 > 39 bool can(const vector<int>& X, int K, int q) > 40 { > 41 int N = X.size(); > 42 for(int mask=0; mask<(1<<N); ++mask) > 43 { > 44 int bc = bitcnt(mask); > 45 if(K==1 && bc==2 || K>=2 && 3<=bc && bc<=1LL<<K) > 46 { > 47 int num = 0x7fffffff; > 48 for(int i=0; i<N; ++i) > 49 if(mask & (1<<i)) > 50 num &= X[i]; > 51 if(num==q) > 52 return true; > 53 } > 54 } > 55 return false; > 56 } > 57 }; > 58 > 59 // BEGIN CUT HERE > 60 #include <ctime> > 61 double start_time; string timer() > 62 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 63 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 64 { os << "{ "; > 65 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 66 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 67 void verify_case(const string& Expected, const string& Received) { > 68 bool ok = (Expected == Received); > 69 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 70 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 71 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 72 #define END verify_case(_, YetAnotherANDProblem().test(X, K, queries));} > 73 int main(){ > 74 > 75 CASE(0) > 76 int X_[] = {10, 14, 7}; > 77 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 78 int K = 1; > 79 int queries_[] = {10, 14, 2, 4}; > 80 vector <int> queries(queries_, queries_+sizeof(queries_)/sizeof(*queri > 81 string _ = "+-+-"; > 82 END > 83 CASE(1) > 84 int X_[] = {30, 29, 27, 23, 15}; > 85 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 86 int K = 2; > 87 int queries_[] = {28, 9, 16, 0, 12}; > 88 vector <int> queries(queries_, queries_+sizeof(queries_)/sizeof(*queri > 89 string _ = "-++-+"; > 90 END > 91 CASE(2) > 92 int X_[] = {5, 5, 5, 5, 5}; > 93 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 94 int K = 50; > 95 int queries_[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; > 96 vector <int> queries(queries_, queries_+sizeof(queries_)/sizeof(*queri > 97 string _ = "-----+----"; > 98 END > 99 CASE(3) > 100 int X_[] = {71258, 1257, 2592588, 2885851, 999928, 123456, 59881, 99999} > 101 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 102 int K = 4; > 103 int queries_[] = {72, 91, 10, 0, 27, 64, 8}; > 104 vector <int> queries(queries_, queries_+sizeof(queries_)/sizeof(*queri > 105 string _ = "+--+-++"; > 106 END > 107 /* > 108 CASE(4) > 109 int X_[] = ; > 110 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 111 int K = ; > 112 int queries_[] = ; > 113 vector <int> queries(queries_, queries_+sizeof(queries_)/sizeof(*queri > 114 string _ = ; > 115 END > 116 CASE(5) > 117 int X_[] = ; > 118 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 119 int K = ; > 120 int queries_[] = ; > 121 vector <int> queries(queries_, queries_+sizeof(queries_)/sizeof(*queri > 122 string _ = ; > 123 END > 124 */ > 125 } > 126 // END CUT HERE
Added SRM/TCO13-3A-U/1B-U.cpp version [6617dfc0554ca885]
> 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<double> CMP; > 21 > 22 const int dy[] = {-1,+1,0,0}; > 23 const int dx[] = {0,0,-1,+1}; > 24 > 25 template<typename T> > 26 class IdGen > 27 { > 28 map<T, int> v2id_; > 29 vector<T> id2v_; > 30 public: > 31 int v2id(const T& v) { > 32 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 33 return v2id_[v]; > 34 } > 35 const T& id2v(int i) const { return id2v_[i]; } > 36 int size() const { return id2v_.size(); } > 37 }; > 38 > 39 template<typename Vert, typename Flow, int NV=2048> > 40 class MaxFlow > 41 { > 42 IdGen<Vert> idgen; > 43 vector<int> G[NV]; > 44 Flow F[NV][NV]; > 45 > 46 public: > 47 void addEdge( Vert s_, Vert t_, Flow f ) > 48 { > 49 const int s = idgen.v2id(s_), t = idgen.v2id(t_); > 50 G[s].push_back(t); > 51 G[t].push_back(s); > 52 F[s][t] = f; > 53 F[t][s] = 0; > 54 } > 55 > 56 Flow calc( Vert s_, Vert t_ ) > 57 { > 58 const int S = idgen.v2id(s_), D = idgen.v2id(t_); > 59 for( Flow total=0 ;; ) { > 60 // Do BFS and compute the level for each node. > 61 int LV[NV] = {0}; > 62 vector<int> Q(1, S); > 63 for(int lv=1; !Q.empty(); ++lv) { > 64 vector<int> Q2; > 65 for(size_t i=0; i!=Q.size(); ++i) { > 66 const vector<int>& ne = G[Q[i]]; > 67 for(size_t j=0; j!=ne.size(); ++j) > 68 if( F[Q[i]][ne[j]] && !LV[ne[j]] > 69 LV[ne[j]]=lv, Q2.push_ba > 70 } > 71 Q.swap(Q2); > 72 } > 73 > 74 // Destination is now unreachable. Done. > 75 if( !LV[D] ) > 76 return total; > 77 > 78 // Iterating DFS. > 79 bool blocked[NV] = {}; > 80 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 81 } > 82 } > 83 > 84 private: > 85 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 86 { > 87 Flow flow_out = 0; > 88 for(size_t i=0; i!=G[v].size(); ++i) { > 89 int u = G[v][i]; > 90 if( LV[v]+1==LV[u] && F[v][u] ) { > 91 Flow f = min(flow_in-flow_out, F[v][u]); > 92 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 93 F[v][u] -= f; > 94 F[u][v] += f; > 95 flow_out += f; > 96 if( flow_in == flow_out ) return flow_ou > 97 } > 98 } > 99 } > 100 blocked[v] = (flow_out==0); > 101 return flow_out; > 102 } > 103 }; > 104 > 105 class Block3Checkers { public: > 106 int blockThem(vector <string> board) > 107 { > 108 int H = board.size(); > 109 int W = board[0].size(); > 110 for(int y=0; y<H; ++y) > 111 for(int x=0; x<W; ++x) > 112 if(board[y][x] == 'A') { > 113 for(int d=0; d<4; ++d) { > 114 int xx = x+dx[d]; > 115 int yy = y+dy[d]; > 116 if(0<=xx&&xx<W&&0<=yy&&yy<H&&board[yy][x > 117 return 100; > 118 } > 119 } > 120 > 121 vector<pair<int,int> > ps, as; > 122 for(int y=0; y<H; ++y) > 123 for(int x=0; x<W; ++x) > 124 if(board[y][x]=='.') > 125 ps.push_back(make_pair(y,x)); > 126 else if(board[y][x]=='A') > 127 as.push_back(make_pair(y,x)); > 128 > 129 vector<vector<int> > rf; > 130 if(ok(board,as,rf)) > 131 return 0; > 132 for(int i=0; i<ps.size(); ++i) { > 133 int y = ps[i].first; > 134 int x = ps[i].second; > 135 board[y][x] = 'N'; > 136 if(ok(board,as,rf)) > 137 return 1; > 138 board[y][x] = '.'; > 139 } > 140 int best = 6; > 141 for(int i=0; i<ps.size(); ++i) > 142 for(int k=i+1; k<ps.size(); ++k) { > 143 int y1 = ps[i].first; > 144 int x1 = ps[i].second; > 145 int y2 = ps[k].first; > 146 int x2 = ps[k].second; > 147 board[y1][x1] = 'N'; > 148 board[y2][x2] = 'N'; > 149 if(ok(board,as,rf)) > 150 return 2; > 151 if(rf[as[0].first][as[0].first] == (1<<0)) > 152 best = min(best, 2+split(board, as[1], as[2])); > 153 if(rf[as[1].first][as[1].first] == (1<<1)) > 154 best = min(best, 2+split(board, as[2], as[0])); > 155 if(rf[as[2].first][as[2].first] == (1<<2)) > 156 best = min(best, 2+split(board, as[0], as[1])); > 157 board[y1][x1] = '.'; > 158 board[y2][x2] = '.'; > 159 } > 160 > 161 return best; > 162 } > 163 > 164 bool ok(const vector<string>& B, vector<pair<int,int> >& as, vector<vect > 165 { > 166 int H = B.size(); > 167 int W = B[0].size(); > 168 rf.assign(H, vector<int>(W, 0)); > 169 for(int i=0; i<as.size(); ++i) > 170 { > 171 int ay = as[i].first; > 172 int ax = as[i].second; > 173 rf[ay][ax] |= (1<<i); > 174 queue<pair<int,int> > q; > 175 q.push(as[i]); > 176 while(!q.empty()) { > 177 int y = q.front().first; > 178 int x = q.front().second; > 179 q.pop(); > 180 for(int d=0; d<4; ++d) { > 181 int yy = y+dy[d]; > 182 int xx = x+dx[d]; > 183 if(0<=yy&&yy<H&&0<=xx&&xx<W&&B[y][x]!='N > 184 rf[yy][xx] |= 1<<i; > 185 q.push(make_pair(yy,xx)); > 186 } > 187 } > 188 } > 189 } > 190 for(int i=0; i<as.size(); ++i) > 191 if(rf[as[i].first][as[i].second] != (1<<i)) > 192 return false; > 193 return true; > 194 } > 195 > 196 int split(const vector<string>& B, pair<int,int> S, pair<int,int> D) > 197 { > 198 int OUT = 0, IN = 1; > 199 typedef pair<int, pair<int,int> > Vert; > 200 MaxFlow<Vert, int>* mf = new MaxFlow<Vert,int>; > 201 int H = B.size(); > 202 int W = B[0].size(); > 203 for(int y=0; y<H; ++y) > 204 for(int x=0; x<W; ++x) > 205 if(B[y][x] != 'N') { > 206 pair<int,int> p(y,x); > 207 for(int d=0; d<4; ++d) { > 208 int xx = x+dx[d]; > 209 int yy = y+dy[d]; > 210 if(0<=xx&&xx<W&&0<=yy&&yy<H&&B[yy][xx]!= > 211 mf->addEdge(make_pair(OUT, p), m > 212 } > 213 if(p!=S && p!=D) > 214 mf->addEdge(make_pair(IN, p), make_pair( > 215 } > 216 int m = mf->calc(make_pair(OUT,S), make_pair(IN,D)); > 217 delete mf; > 218 return m; > 219 } > 220 }; > 221 > 222 // BEGIN CUT HERE > 223 #include <ctime> > 224 double start_time; string timer() > 225 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 226 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 227 { os << "{ "; > 228 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 229 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 230 void verify_case(const int& Expected, const int& Received) { > 231 bool ok = (Expected == Received); > 232 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 233 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 234 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 235 #define END verify_case(_, Block3Checkers().blockThem(board));} > 236 int main(){ > 237 > 238 CASE(0) > 239 string board_[] = {"A......A", > 240 "...N.N..", > 241 ".NNN.NN.", > 242 "NNNN.N.N", > 243 "N.NN.NNN", > 244 ".NNN.NNN", > 245 "NNN...NN", > 246 ".NN.A..N"}; > 247 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 248 int _ = 1; > 249 END > 250 CASE(1) > 251 string board_[] = {".....A", > 252 "......", > 253 "......", > 254 "NNNNNN", > 255 "A.....", > 256 "A....."}; > 257 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 258 int _ = 100; > 259 END > 260 CASE(2) > 261 string board_[] = {"A.N", > 262 "NNA", > 263 "AN."}; > 264 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 265 int _ = 0; > 266 END > 267 CASE(3) > 268 string board_[] = {"......NA", > 269 ".NNNN.N.", > 270 ".N......", > 271 "....NNNN", > 272 "........", > 273 ".N..NNN.", > 274 "......N.", > 275 "A.N....A"} > 276 ; > 277 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 278 int _ = 3; > 279 END > 280 /* > 281 CASE(4) > 282 string board_[] = ; > 283 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 284 int _ = ; > 285 END > 286 CASE(5) > 287 string board_[] = ; > 288 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 289 int _ = ; > 290 END > 291 */ > 292 } > 293 // END CUT HERE