Overview
| SHA1 Hash: | 40c16bd858f6a6142ade72b9c369b0b200c5204a |
|---|---|
| Date: | 2012-04-11 10:47:53 |
| User: | kinaba |
| Comment: | 539 |
| 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/539-U/1A.cpp version [ab9100cd4e760130]
> 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 Over9000Rocks { public: > 29 int countPossibilities(vector <int> lowerBound, vector <int> upperBound) > 30 { > 31 vector< pair<int,bool> > ev; > 32 const int MIN = 9001; > 33 const int N = lowerBound.size(); > 34 for(int mask=1; mask<(1<<N); ++mask) > 35 { > 36 int lo=0, hi=0; > 37 for(int i=0; i<N; ++i) > 38 if( mask & (1<<i) ) { > 39 lo += lowerBound[i]; > 40 hi += upperBound[i]; > 41 } > 42 if(hi<MIN) > 43 continue; > 44 lo = max(lo, MIN); > 45 ev.push_back( make_pair(lo,true) ); > 46 ev.push_back( make_pair(hi+1,false) ); > 47 } > 48 sort(ev.begin(), ev.end()); > 49 int nest = 0; > 50 int entered = -1; > 51 int total = 0; > 52 for(int k=0; k<ev.size(); ++k) > 53 { > 54 int x = ev[k].first; > 55 bool in = ev[k].second; > 56 if( nest == 0 ) { > 57 if( in ) > 58 entered = x; > 59 } else if( nest == 1 ) { > 60 if( !in ) > 61 total += (x - entered); > 62 } > 63 if(in) nest++; else nest--; > 64 } > 65 return total; > 66 } > 67 }; > 68 > 69 // BEGIN CUT HERE > 70 #include <ctime> > 71 double start_time; string timer() > 72 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 73 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 74 { os << "{ "; > 75 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 76 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 77 void verify_case(const int& Expected, const int& Received) { > 78 bool ok = (Expected == Received); > 79 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 80 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 81 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 82 #define END verify_case(_, Over9000Rocks().countPossibilities(lowerBound, u > 83 int main(){ > 84 > 85 CASE(0) > 86 int lowerBound_[] = {9000}; > 87 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 88 int upperBound_[] = {9001}; > 89 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 90 int _ = 1; > 91 END > 92 CASE(1) > 93 int lowerBound_[] = {9000, 1, 10}; > 94 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 95 int upperBound_[] = {9000, 2, 20}; > 96 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 97 int _ = 15; > 98 END > 99 CASE(2) > 100 int lowerBound_[] = {1001, 2001, 3001, 3001}; > 101 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 102 int upperBound_[] = {1003, 2003, 3003, 3003}; > 103 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 104 int _ = 9; > 105 END > 106 CASE(3) > 107 int lowerBound_[] = {9000,90000,1,10}; > 108 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 109 int upperBound_[] = {9000,90000,3,15}; > 110 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 111 int _ = 38; > 112 END > 113 CASE(4) > 114 int lowerBound_[] = {1,1,1,1,1,1}; > 115 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 116 int upperBound_[] = {3,4,5,6,7,8}; > 117 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 118 int _ = 0; > 119 END > 120 CASE(5) > 121 int lowerBound_[] = {242,7393,3738,2594,3051,7711,3386,4363,6035,4752,53 > 122 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 123 int upperBound_[] = {9138,9120,9027,9185,9081,9114,9044,9089,9178,9103,9 > 124 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 125 int _ = -1; > 126 END > 127 CASE(6) > 128 int lowerBound_[] = {9001}; > 129 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 130 int upperBound_[] = {9002}; > 131 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 132 int _ = 2; > 133 END > 134 CASE(7) > 135 int lowerBound_[] = {9000, 1, 2, 3}; > 136 vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/s > 137 int upperBound_[] = {9000, 1, 2, 3}; > 138 vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/s > 139 int _ = 10; > 140 END > 141 > 142 } > 143 // END CUT HERE
Added SRM/539-U/1B-U.cpp version [fb6029affb2ad4b9]
> 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 static const int INF = 0x3fffffff; > 29 > 30 typedef int vert; > 31 typedef vert edge; > 32 typedef vector<edge> edges; > 33 typedef vector<edges> graph; > 34 > 35 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) > 36 { > 37 for(int i=0; i<G[v].size(); ++i) { > 38 vert u = G[v][i]; > 39 if( visited[u] ) continue; > 40 visited[u] = true; > 41 > 42 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) > 43 { matchTo[v]=u, matchTo[u]=v; return true; } > 44 } > 45 return false; > 46 } > 47 > 48 template<int NV> > 49 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right > 50 // only left->right edges are used during computation > 51 { > 52 vector<vert> matchTo(G.size(), -1); > 53 int ans = 0; > 54 for(vert v=0; v<L; ++v) { > 55 bool visited[NV] = {}; > 56 if( augment(G, v, matchTo, visited) ) > 57 ++ans; > 58 } > 59 return ans; > 60 } > 61 > 62 class SafeReturn { public: > 63 int minRisk(int N, vector <string> streets) > 64 { > 65 int T = streets.size(); > 66 vector< vector<int> > g(T, vector<int>(T, INF)); > 67 for(int i=0; i<T; ++i) > 68 for(int j=0; j<T; ++j) > 69 if( i == j ) > 70 g[i][j] = 0; > 71 else if( streets[i][j] != '-' ) > 72 g[i][j] = streets[i][j] - '0'; > 73 vector< vector<int> > d = g; > 74 for(int k=0; k<T; ++k) > 75 for(int i=0; i<T; ++i) > 76 for(int j=0; j<T; ++j) > 77 d[i][j] = min(d[i][j], d[i][k]+d[k][j]); > 78 > 79 graph G(2*(N+1)); > 80 for(int x=0; x<=N; ++x) > 81 for(int y=0; y<=N; ++y) if( x != y ) > 82 { > 83 if( d[0][x] + d[x][y] == d[0][y] ) > 84 { > 85 G[x].push_back(N+1+y); > 86 } > 87 } > 88 return N+1 - biMatch<256>(G, N+1); > 89 } > 90 }; > 91 > 92 // BEGIN CUT HERE > 93 #include <ctime> > 94 double start_time; string timer() > 95 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 96 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 97 { os << "{ "; > 98 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 99 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 100 void verify_case(const int& Expected, const int& Received) { > 101 bool ok = (Expected == Received); > 102 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 103 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 104 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 105 #define END verify_case(_, SafeReturn().minRisk(N, streets));} > 106 int main(){ > 107 > 108 CASE(0) > 109 int N = 3; > 110 string streets_[] = {"-234", > 111 "2---", > 112 "3---", > 113 "4---"}; > 114 vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*st > 115 int _ = 3; > 116 END > 117 CASE(1) > 118 int N = 2; > 119 string streets_[] = {"-12", > 120 "1-1", > 121 "21-"}; > 122 vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*st > 123 int _ = 1; > 124 END > 125 CASE(2) > 126 int N = 3; > 127 string streets_[] = {"-----7", > 128 "--1---", > 129 "-1-5--", > 130 "--5-1-", > 131 "---1-3", > 132 "7---3-"}; > 133 vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*st > 134 int _ = 1; > 135 END > 136 CASE(3) > 137 int N = 2; > 138 string streets_[] = {"-11", > 139 "1-1", > 140 "11-"}; > 141 vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*st > 142 int _ = 2; > 143 END > 144 /* > 145 CASE(4) > 146 int N = ; > 147 string streets_[] = ; > 148 vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*st > 149 int _ = ; > 150 END > 151 CASE(5) > 152 int N = ; > 153 string streets_[] = ; > 154 vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*st > 155 int _ = ; > 156 END > 157 */ > 158 } > 159 // END CUT HERE
Added SRM/539-U/1C-U.cpp version [73a81491ebb9328c]
> 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 template<typename T> > 29 class IdGen > 30 { > 31 map<T, int> v2id_; > 32 vector<T> id2v_; > 33 public: > 34 int v2id(const T& v) { > 35 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 36 return v2id_[v]; > 37 } > 38 const T& id2v(int i) const { return id2v_[i]; } > 39 int size() const { return id2v_.size(); } > 40 }; > 41 > 42 typedef int vert; > 43 typedef vert edge; > 44 typedef vector<edge> edges; > 45 typedef vector<edges> graph; > 46 > 47 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) > 48 { > 49 for(int i=0; i<G[v].size(); ++i) { > 50 vert u = G[v][i]; > 51 if( visited[u] ) continue; > 52 visited[u] = true; > 53 > 54 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) > 55 { matchTo[v]=u, matchTo[u]=v; return true; } > 56 } > 57 return false; > 58 } > 59 > 60 template<int NV> > 61 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right > 62 // only left->right edges are used during computation > 63 { > 64 vector<vert> matchTo(G.size(), -1); > 65 int ans = 0; > 66 for(vert v=0; v<L; ++v) { > 67 bool visited[NV] = {}; > 68 if( augment(G, v, matchTo, visited) ) > 69 ++ans; > 70 } > 71 return ans; > 72 } > 73 > 74 class FoxBomb { public: > 75 int getMinimumCost(vector <string> grid) > 76 { > 77 int H = grid.size(); > 78 int W = grid[0].size(); > 79 > 80 IdGen< pair< int,pair<int,int> > > hline; > 81 for(int y=0; y<H; ++y) > 82 for(int sx=0; sx<W; ) > 83 { > 84 if( grid[y][sx] == '#' ) > 85 {++sx; continue;} > 86 int ex = sx+1; > 87 for(; ex<W && grid[y][ex]=='.'; ++ex) {} > 88 if( sx+1 < ex ) > 89 hline.v2id( make_pair(y, make_pair(sx,ex > 90 sx = ex; > 91 } > 92 > 93 IdGen< pair< int,pair<int,int> > > vline; > 94 for(int x=0; x<W; ++x) > 95 for(int sy=0; sy<H; ) > 96 { > 97 if( grid[sy][x] == '#' ) > 98 {++sy; continue;} > 99 int ey = sy+1; > 100 for(; ey<H && grid[ey][x]=='.'; ++ey) {} > 101 if( sy+1 < ey ) > 102 vline.v2id( make_pair(x, make_pair(sy,ey > 103 sy = ey; > 104 } > 105 > 106 graph G(hline.size() + vline.size()); > 107 for(int i=0; i<hline.size(); ++i) > 108 for(int k=0; k<vline.size(); ++k) > 109 { > 110 const pair< int,pair<int,int> >& hh = hline.id2v > 111 const pair< int,pair<int,int> >& vv = vline.id2v > 112 int y = hh.first; > 113 int sx = hh.second.first; > 114 int ex = hh.second.second; > 115 int x = vv.first; > 116 int sy = vv.second.first; > 117 int ey = vv.second.second; > 118 if( sx<=x && x<ex && sy<=y && y<ey ) > 119 G[i].push_back(hline.size()+k); > 120 } > 121 > 122 int dots = 0; > 123 for(int y=0; y<H; ++y) > 124 for(int x=0; x<W; ++x) if( grid[y][x]=='.' ) > 125 { > 126 int dy[]={-1,+1,0,0}; > 127 int dx[]={0,0,-1,+1}; > 128 bool non_wall = false; > 129 for(int i=0; i<4; ++i) { > 130 int yy = y+dy[i]; > 131 int xx = x+dx[i]; > 132 if(0<=yy&&yy<H&&0<=xx&&xx<W&&grid[yy][xx > 133 non_wall = true; > 134 } > 135 if(!non_wall) > 136 dots++; > 137 } > 138 > 139 return dots + G.size() - biMatch<2500>(G, hline.size()); > 140 } > 141 }; > 142 > 143 // BEGIN CUT HERE > 144 #include <ctime> > 145 double start_time; string timer() > 146 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 147 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 148 { os << "{ "; > 149 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 150 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 151 void verify_case(const int& Expected, const int& Received) { > 152 bool ok = (Expected == Received); > 153 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 154 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 155 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 156 #define END verify_case(_, FoxBomb().getMinimumCost(grid));} > 157 int main(){ > 158 > 159 CASE(0) > 160 string grid_[] = {"#..." > 161 ,"..##" > 162 ,"#.##"}; > 163 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 164 int _ = 2; > 165 END > 166 CASE(1) > 167 string grid_[] = {".#.#.#." > 168 ,"......." > 169 ,".#.#.#."}; > 170 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 171 int _ = 4; > 172 END > 173 CASE(2) > 174 string grid_[] = {"######################################" > 175 ,"######################################" > 176 ,"###.....................##############" > 177 ,"###.###################.###....#...###" > 178 ,"###.###################.###.######.###" > 179 ,"###.###################.###.######.###" > 180 ,"###.###################.###.######.###" > 181 ,"###.###################.###.######.###" > 182 ,"###.###################.###.######.###" > 183 ,"###.........####........###.######.###" > 184 ,"###########.###########.###........###" > 185 ,"###########.###########.##########.###" > 186 ,"###########.###########.##########.###" > 187 ,"###########.###########.##########.###" > 188 ,"###########.###########.##########.###" > 189 ,"##..........##..........##########.###" > 190 ,"#######################............###" > 191 ,"######################################"}; > 192 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 193 int _ = 9; > 194 END > 195 CASE(3) > 196 string grid_[] = {".#." > 197 ,"..." > 198 ,"#.#" > 199 ,"..." > 200 ,".#."} > 201 ; > 202 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 203 int _ = 5; > 204 END > 205 CASE(4) > 206 string grid_[] = {"."}; > 207 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 208 int _ = 1; > 209 END > 210 CASE(5) > 211 string grid_[] = {"..."}; > 212 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 213 int _ = 1; > 214 END > 215 CASE(6) > 216 string grid_[] = {".",".","."}; > 217 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 218 int _ = 1; > 219 END > 220 CASE(7) > 221 string grid_[] = { > 222 "...#.", > 223 "####.", > 224 "...#."}; > 225 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 226 int _ = 3; > 227 END > 228 } > 229 // END CUT HERE