Overview
| SHA1 Hash: | 98c5c562cad400991afc3583078a0d7c80545d00 |
|---|---|
| Date: | 2015-02-02 11:21:02 |
| User: | kinaba |
| Comment: | 645 |
| 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/645-U/1A.cpp version [2a313f584cf9e5c7]
> 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 TheConsecutiveIntegersDivOne { public: > 23 int find(vector <int> numbers, int k) > 24 { > 25 sort(numbers.begin(), numbers.end()); > 26 int best = 0x7fffffff; > 27 for(int fixed=0; fixed<numbers.size(); ++fixed) { > 28 for(int s=0; s+k<=numbers.size(); ++s) { > 29 if(s<=fixed && fixed<=s+k) { > 30 int cost = 0; > 31 for(int i=0; i<k; ++i) > 32 cost += abs(numbers[s+i] - (numb > 33 best = min(best, cost); > 34 } > 35 } > 36 } > 37 return best; > 38 } > 39 }; > 40 > 41 // BEGIN CUT HERE > 42 #include <ctime> > 43 double start_time; string timer() > 44 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 45 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 46 { os << "{ "; > 47 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 48 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 49 void verify_case(const int& Expected, const int& Received) { > 50 bool ok = (Expected == Received); > 51 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 52 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 53 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 54 #define END verify_case(_, TheConsecutiveIntegersDivOne().find(numbers, k)) > 55 int main(){ > 56 > 57 CASE(0) > 58 int numbers_[] = {4, 7, 47}; > 59 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 60 int k = 2; > 61 int _ = 2; > 62 END > 63 CASE(1) > 64 int numbers_[] = {1, 100}; > 65 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 66 int k = 1; > 67 int _ = 0; > 68 END > 69 CASE(2) > 70 int numbers_[] = {-96, -53, 82, -24, 6, -75}; > 71 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 72 int k = 2; > 73 int _ = 20; > 74 END > 75 CASE(3) > 76 int numbers_[] = {64, -31, -56}; > 77 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 78 int k = 2; > 79 int _ = 24; > 80 END > 81 CASE(4) > 82 int numbers_[] = {-96, -53, 82, -24, 6, -75}; > 83 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 84 int k = 4; > 85 int _ = 90; > 86 END > 87 /* > 88 CASE(5) > 89 int numbers_[] = ; > 90 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 91 int k = ; > 92 int _ = ; > 93 END > 94 CASE(6) > 95 int numbers_[] = ; > 96 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 97 int k = ; > 98 int _ = ; > 99 END > 100 */ > 101 } > 102 // END CUT HERE
Added SRM/645-U/2B-U.cpp version [d58d04c710b03f7f]
> 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 TheGridDivOne { public: > 23 int find(vector <int> x, vector <int> y, int k) > 24 { > 25 enum {X, Y}; > 26 typedef tuple<int,int> Point; > 27 > 28 set<Point> blocked; > 29 map<int, set<int>> x2y; > 30 x2y[0].emplace(0); > 31 for(int i=0; i<x.size(); ++i) { > 32 blocked.emplace(x[i], y[i]); > 33 x2y[x[i]-1].emplace(y[i]-1); > 34 x2y[x[i]-1].emplace(y[i]+0); > 35 x2y[x[i]-1].emplace(y[i]+1); > 36 x2y[x[i]+0].emplace(y[i]-1); > 37 x2y[x[i]+0].emplace(y[i]+1); > 38 x2y[x[i]+1].emplace(y[i]-1); > 39 x2y[x[i]+1].emplace(y[i]+0); > 40 x2y[x[i]+1].emplace(y[i]+1); > 41 } > 42 > 43 map<int, set<int>> x2y_aug = x2y; > 44 for(auto it=x2y.begin(); it!=x2y.end(); ++it) { > 45 auto kt = it; ++kt; > 46 if(kt != x2y.end()) { > 47 for(int y: it->second) > 48 x2y_aug[kt->first].emplace(y); > 49 } > 50 if(it != x2y.begin()) { > 51 auto kt = it; --kt; > 52 for(int y: it->second) > 53 x2y_aug[kt->first].emplace(y); > 54 } > 55 } > 56 > 57 vector<Point> pts; > 58 for(auto& xys: x2y_aug) { > 59 int x = xys.first; > 60 for(int y: xys.second) { > 61 Point q(x,y); > 62 if(!blocked.count(q)) > 63 pts.emplace_back(q); > 64 } > 65 } > 66 > 67 typedef int Vert; > 68 const int N = pts.size(); > 69 const int S = std::find(pts.begin(), pts.end(), Point(0,0)) - pt > 70 typedef int Cost; > 71 typedef pair<Cost,Vert> Edge; > 72 typedef vector<Edge> Edges; > 73 typedef vector<Edges> Graph; > 74 > 75 Graph G(N); > 76 for(int i=0; i<N; ++i) > 77 for(int k=i+1; k<N; ++k) { > 78 bool connected = true; > 79 int x1 = get<X>(pts[i]); > 80 int x2 = get<X>(pts[k]); > 81 int y1 = get<Y>(pts[i]); > 82 int y2 = get<Y>(pts[k]); > 83 for(Point b: blocked) { > 84 if(min(y1,y2)<=get<Y>(b) && get<Y>(b)<=max(y1,y2 > 85 min(x1,x2)<=get<X>(b) && get<X>(b)<=max(x1,x2 > 86 connected = false; > 87 break; > 88 } > 89 } > 90 // If not blocked then add i<-->k with Manhattan cost > 91 if(connected) { > 92 G[i].emplace_back(abs(x1-x2)+abs(y1-y2), k); > 93 G[k].emplace_back(abs(x1-x2)+abs(y1-y2), i); > 94 } > 95 } > 96 > 97 // Dijkstra > 98 priority_queue<Edge, vector<Edge>, greater<Edge>> Q; > 99 Q.emplace(0, S); > 100 vector<Cost> D(N, -1); > 101 while(!Q.empty()) { > 102 Cost c = Q.top().first; > 103 Vert v = Q.top().second; > 104 Q.pop(); > 105 if(D[v]!=-1) > 106 continue; > 107 D[v] = c; > 108 > 109 for(auto e: G[v]) { > 110 Cost c2 = c + e.first; > 111 Vert q = e.second; > 112 if(D[q]==-1) > 113 Q.emplace(c2, q); > 114 } > 115 } > 116 > 117 int best = 0; > 118 for(Vert v=0; v<N; ++v) { > 119 if(D[v] != -1 && D[v]<=k) { > 120 // the point > 121 best = max(best, get<X>(pts[v])); > 122 > 123 > 124 // if not blocked... > 125 Point right(get<X>(pts[v])+1, get<Y>(pts[v])); > 126 if(blocked.count(right)) > 127 continue; > 128 > 129 // go more east > 130 bool skip = false; > 131 for(Edge e: G[v]) { > 132 Vert u = e.second; > 133 if(get<Y>(pts[u]) == get<Y>(pts[v]) && g > 134 && D[u]!=-1 && D[u]<=k) { > 135 skip = true; > 136 } > 137 } > 138 if(!skip) { > 139 int sec = k-D[v]; > 140 best = max(best, get<X>(pts[v]) + sec); > 141 } > 142 } > 143 } > 144 > 145 return best; > 146 } > 147 }; > 148 > 149 // BEGIN CUT HERE > 150 #include <ctime> > 151 double start_time; string timer() > 152 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 153 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 154 { os << "{ "; > 155 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 156 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 157 void verify_case(const int& Expected, const int& Received) { > 158 bool ok = (Expected == Received); > 159 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 160 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 161 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 162 #define END verify_case(_, TheGridDivOne().find(x, y, k));} > 163 int main(){ > 164 > 165 CASE(0) > 166 int x_[] = {1,1,1,1}; > 167 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 168 int y_[] = {-2,-1,0,1}; > 169 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 170 int k = 4; > 171 int _ = 2; > 172 END > 173 CASE(1) > 174 int x_[] = {-1, 0, 0, 1}; > 175 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 176 int y_[] = {0, -1, 1, 0}; > 177 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 178 int k = 9; > 179 int _ = 0; > 180 END > 181 CASE(2) > 182 vector <int> x; > 183 vector <int> y; > 184 int k = 1000; > 185 int _ = 1000; > 186 END > 187 CASE(3) > 188 int x_[] = {1,0,0,-1,-1,-2,-2,-3,-3,-4,-4}; > 189 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 190 int y_[] = {0,-1,1,-2,2,-3,3,-4,4,-5,5}; > 191 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 192 int k = 47; > 193 int _ = 31; > 194 END > 195 /* > 196 CASE(4) > 197 int x_[] = ; > 198 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 199 int y_[] = ; > 200 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 201 int k = ; > 202 int _ = ; > 203 END > 204 CASE(5) > 205 int x_[] = ; > 206 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 207 int y_[] = ; > 208 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 209 int k = ; > 210 int _ = ; > 211 END > 212 */ > 213 } > 214 // END CUT HERE