Overview
| SHA1 Hash: | ba015e921778068c4622d2420e81abe9fffb0a53 |
|---|---|
| Date: | 2014-10-04 14:48:03 |
| User: | kinaba |
| Comment: | 634 |
| 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/634-U/1A.cpp version [9fbd3a306518e9ad]
> 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 ShoppingSurveyDiv1 { public: > 23 int minValue(int N, int K, vector <int> s) > 24 { > 25 for(int big=0; big<=N; ++big) > 26 if(can(N, K, s, big)) > 27 return big; > 28 > 29 assert(false); > 30 return -1; > 31 } > 32 > 33 bool can(int N, int K, vector<int> sb, int BIG) > 34 { > 35 sort(sb.rbegin(), sb.rend()); > 36 assert(sb[K-1] >= BIG); > 37 > 38 multiset<int, greater<int>> s; > 39 for(auto p: sb) > 40 if(p-BIG > 0) > 41 s.insert(p-BIG); > 42 int total = accumulate(s.begin(), s.end(), 0); > 43 if(total > (K-1)*(N-BIG)) > 44 return false; > 45 if(!s.empty() && *s.begin() > (N-BIG)) > 46 return false; > 47 return true; > 48 } > 49 }; > 50 > 51 // BEGIN CUT HERE > 52 #include <ctime> > 53 double start_time; string timer() > 54 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 55 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 56 { os << "{ "; > 57 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 58 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 59 void verify_case(const int& Expected, const int& Received) { > 60 bool ok = (Expected == Received); > 61 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 62 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 63 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 64 #define END verify_case(_, ShoppingSurveyDiv1().minValue(N, K, s));} > 65 int main(){ > 66 > 67 CASE(0) > 68 int N = 10; > 69 int K = 2; > 70 int s_[] = {1, 2, 3}; > 71 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 72 int _ = 0; > 73 END > 74 CASE(1) > 75 int N = 5; > 76 int K = 2; > 77 int s_[] = {1, 2, 3}; > 78 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 79 int _ = 1; > 80 END > 81 CASE(2) > 82 int N = 4; > 83 int K = 4; > 84 int s_[] = {4, 4, 4, 2}; > 85 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 86 int _ = 2; > 87 END > 88 CASE(3) > 89 int N = 20; > 90 int K = 3; > 91 int s_[] = {1, 10, 3, 4, 8, 15, 3, 16, 18, 2, 7, 3}; > 92 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 93 int _ = 10; > 94 END > 95 CASE(4) > 96 int N = 4; > 97 int K = 2; > 98 int s_[] = {1, 2, 1, 1, 3, 1, 2, 2, 1, 2, 1}; > 99 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 100 int _ = 2; > 101 END > 102 CASE(5) > 103 int N = 2; > 104 int K = 3; > 105 int s_[] = {1, 1, 1, 2}; > 106 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 107 int _ = 1; > 108 END > 109 CASE(6) > 110 int N = 500; > 111 int K = 1; > 112 int s_[] = {500,500,500,500,500,500,500,500,500,500,500,500,500,500,500, > 113 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 114 int _ = -1; > 115 END > 116 CASE(6) > 117 int N = 500; > 118 int K = 500; > 119 int s_[] = {500,500,500,500,500,500,500,500,500,500,500,500,500,500,500, > 120 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 121 int _ = -1; > 122 END > 123 } > 124 // END CUT HERE
Added SRM/634-U/1B.cpp version [3a56668afe2cfe71]
> 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 > 21 template<typename T> > 22 class IdGen > 23 { > 24 map<T, int> v2id_; > 25 vector<T> id2v_; > 26 public: > 27 int v2id(const T& v) { > 28 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 29 return v2id_[v]; > 30 } > 31 const T& id2v(int i) const { return id2v_[i]; } > 32 int size() const { return id2v_.size(); } > 33 }; > 34 > 35 template<typename Vert, typename Flow, int NV=2048> > 36 class MaxFlow > 37 { > 38 IdGen<Vert> idgen; > 39 vector<int> G[NV]; > 40 Flow F[NV][NV]; > 41 > 42 public: > 43 void addEdge( Vert s_, Vert t_, Flow f ) > 44 { > 45 const int s = idgen.v2id(s_), t = idgen.v2id(t_); > 46 G[s].push_back(t); > 47 G[t].push_back(s); > 48 F[s][t] = f; > 49 F[t][s] = 0; > 50 } > 51 > 52 Flow calc( Vert s_, Vert t_ ) > 53 { > 54 const int S = idgen.v2id(s_), D = idgen.v2id(t_); > 55 for( Flow total=0 ;; ) { > 56 // Do BFS and compute the level for each node. > 57 int LV[NV] = {0}; > 58 vector<int> Q(1, S); > 59 for(int lv=1; !Q.empty(); ++lv) { > 60 vector<int> Q2; > 61 for(size_t i=0; i!=Q.size(); ++i) { > 62 const vector<int>& ne = G[Q[i]]; > 63 for(size_t j=0; j!=ne.size(); ++j) > 64 if( F[Q[i]][ne[j]] && !LV[ne[j]] > 65 LV[ne[j]]=lv, Q2.push_ba > 66 } > 67 Q.swap(Q2); > 68 } > 69 > 70 // Destination is now unreachable. Done. > 71 if( !LV[D] ) > 72 return total; > 73 > 74 // Iterating DFS. > 75 bool blocked[NV] = {}; > 76 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 77 } > 78 } > 79 > 80 private: > 81 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 82 { > 83 Flow flow_out = 0; > 84 for(size_t i=0; i!=G[v].size(); ++i) { > 85 int u = G[v][i]; > 86 if( LV[v]+1==LV[u] && F[v][u] ) { > 87 Flow f = min(flow_in-flow_out, F[v][u]); > 88 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 89 F[v][u] -= f; > 90 F[u][v] += f; > 91 flow_out += f; > 92 if( flow_in == flow_out ) return flow_ou > 93 } > 94 } > 95 } > 96 blocked[v] = (flow_out==0); > 97 return flow_out; > 98 } > 99 }; > 100 > 101 > 102 typedef complex<int> CMP; > 103 double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } > 104 double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); } > 105 int ccw(const CMP& a, CMP b, CMP c) { > 106 b -= a; c -= a; > 107 if( outer_prod(b,c) > 0 ) return +1; // counter clockwise > 108 if( outer_prod(b,c) < 0 ) return -1; // clockwise > 109 if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line > 110 if( norm(b) < norm(c) ) return -2; // [a--b]--c on line > 111 return 0; // [a--c--b] on line > 112 } > 113 > 114 bool cross(int x1, int y1, int x2, int y2, > 115 int X1, int Y1, int X2, int Y2) { > 116 CMP p1(x1,y1); > 117 CMP p2(x2,y2); > 118 CMP P1(X1,Y1); > 119 CMP P2(X2,Y2); > 120 return ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0; > 121 } > 122 > 123 class SegmentDrawing { public: > 124 enum TAG {SRC, LEFT_R, RIGHT_R, LEFT_B, RIGHT_B, DST}; > 125 static const int INF = 0x3fffffff; > 126 > 127 int maxScore(vector <int> x, vector <int> y, vector <int> redScore, vect > 128 { > 129 const int N = x.size(); > 130 > 131 vector<vector<bool>> cross_table(N*N, vector<bool>(N*N)); > 132 for(int i=0; i<N; ++i) > 133 for(int k=i+1; k<N; ++k) > 134 for(int ii=0; ii<N; ++ii) > 135 for(int kk=ii+1; kk<N; ++kk) > 136 cross_table[i*N+k][ii*N+kk] = cross(x[i],y[i],x[k],y[k], > 137 > 138 auto* mf = new MaxFlow<pair<TAG,int>, LL>; > 139 > 140 int all = 0; > 141 for(int i=0; i<N; ++i) > 142 for(int k=i+1; k<N; ++k) { > 143 int p = i*N + k; > 144 mf->addEdge(make_pair(SRC,0), make_pair(LEFT_R,p), redSc > 145 mf->addEdge(make_pair(LEFT_R,p), make_pair(RIGHT_R,p), I > 146 mf->addEdge(make_pair(RIGHT_R,p), make_pair(DST,0), 0); > 147 mf->addEdge(make_pair(SRC,0), make_pair(LEFT_B,p), 0); > 148 mf->addEdge(make_pair(LEFT_B,p), make_pair(RIGHT_B,p), I > 149 mf->addEdge(make_pair(RIGHT_B,p), make_pair(DST,0), blue > 150 all += redScore[p]; > 151 all += blueScore[p]; > 152 } > 153 > 154 for(int i=0; i<N; ++i) > 155 for(int k=i+1; k<N; ++k) > 156 for(int ii=0; ii<N; ++ii) > 157 for(int kk=ii+1; kk<N; ++kk) { > 158 int rp = i*N + k; > 159 int bp = ii*N + kk; > 160 if(cross_table[rp][bp]) > 161 mf->addEdge(make_pair(RIGHT_R,rp), make_pair(LEF > 162 } > 163 > 164 LL flow = mf->calc(make_pair(SRC,0), make_pair(DST,0)); > 165 delete mf; > 166 return all - flow; > 167 } > 168 }; > 169 > 170 // BEGIN CUT HERE > 171 #include <ctime> > 172 double start_time; string timer() > 173 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 174 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 175 { os << "{ "; > 176 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 177 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 178 void verify_case(const int& Expected, const int& Received) { > 179 bool ok = (Expected == Received); > 180 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 181 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 182 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 183 #define END verify_case(_, SegmentDrawing().maxScore(x, y, redScore, blueSc > 184 int main(){ > 185 > 186 CASE(0) > 187 int x_[] = {0,1,0,-1}; > 188 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 189 int y_[] = {1,0,-1,0}; > 190 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 191 int redScore_[] = {0, 1, 2, 3, > 192 1, 0, 6, 4, > 193 2, 6, 0, 5, > 194 3, 4, 5, 0}; > 195 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 196 int blueScore_[] = {0, 2, 3, 7, > 197 2, 0, 4, 6, > 198 3, 4, 0, 5, > 199 7, 6, 5, 0}; > 200 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 201 int _ = 27; > 202 END > 203 CASE(1) > 204 int x_[] = {0, 1}; > 205 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 206 int y_[] = {1, 0}; > 207 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 208 int redScore_[] = {0, 101, 101, 0}; > 209 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 210 int blueScore_[] = {0, 100, 100, 0}; > 211 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 212 int _ = 101; > 213 END > 214 CASE(2) > 215 int x_[] = {-3, -1, -1, 1, 1, 3}; > 216 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 217 int y_[] = { 0, -2, 2, -2, 2, 0}; > 218 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 219 int redScore_[] = {0, 2, 1, 2, 1, 2, > 220 2, 0, 2, 1, 2, 1, > 221 1, 2, 0, 2, 1, 2, > 222 2, 1, 2, 0, 2, 1, > 223 1, 2, 1, 2, 0, 2, > 224 2, 1, 2, 1, 2, 0}; > 225 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 226 int blueScore_[] = {0, 0, 0, 0, 0, 0, > 227 0, 0, 0, 0, 0, 0, > 228 0, 0, 0, 21, 0, 0, > 229 0, 0, 21, 0, 0, 0, > 230 0, 0, 0, 0, 0, 0, > 231 0, 0, 0, 0, 0, 0}; > 232 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 233 int _ = 25; > 234 END > 235 CASE(3) > 236 int x_[] = {-100, 100, 0, -10, 10, 0}; > 237 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 238 int y_[] = {0, 0, 100, 10, 10, 1}; > 239 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 240 int redScore_[] = { 0, 96, 96, 25, 25, 25, > 241 96, 0, 96, 25, 25, 25, > 242 96, 96, 0, 25, 25, 25, > 243 25, 25, 25, 0, 10, 10, > 244 25, 25, 25, 10, 0, 10, > 245 25, 25, 25, 10, 10, 0}; > 246 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 247 int blueScore_[] = { 0, 30, 30, 20, 20, 20, > 248 30, 0, 30, 20, 20, 20, > 249 30, 30, 0, 20, 20, 20, > 250 20, 20, 20, 0, 86, 86, > 251 20, 20, 20, 86, 0, 86, > 252 20, 20, 20, 86, 86, 0}; > 253 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 254 int _ = 546; > 255 END > 256 CASE(4) > 257 int x_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; > 258 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 259 int y_[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}; > 260 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 261 int redScore_[] = {0, 15, 2, 3, 4, 5, 6, 7, 8, 9, > 262 15, 0, 15, 2, 3, 4, 5, 6, 7, 8, > 263 2, 15, 0, 15, 2, 3, 4, 5, 6, 7, > 264 3, 2, 15, 0, 15, 2, 3, 4, 5, 6, > 265 4, 3, 2, 15, 0, 15, 2, 3, 4, 5, > 266 5, 4, 3, 2, 15, 0, 15, 2, 3, 4, > 267 6, 5, 4, 3, 2, 15, 0, 15, 2, 3, > 268 7, 6, 5, 4, 3, 2, 15, 0, 15, 2, > 269 8, 7, 6, 5, 4, 3, 2, 15, 0, 15, > 270 9, 8, 7, 6, 5, 4, 3, 2, 15, 0} > 271 ; > 272 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 273 int blueScore_[] = {0, 0, 2, 3, 4, 5, 6, 7, 8, 9, > 274 0, 0, 0, 2, 3, 4, 5, 6, 7, 8, > 275 2, 0, 0, 0, 2, 3, 4, 5, 6, 7, > 276 3, 2, 0, 0, 0, 2, 3, 4, 5, 6, > 277 4, 3, 2, 0, 0, 100, 2, 3, 4, 5, > 278 5, 4, 3, 2, 100, 0, 0, 2, 3, 4, > 279 6, 5, 4, 3, 2, 0, 0, 0, 2, 3, > 280 7, 6, 5, 4, 3, 2, 0, 0, 0, 2, > 281 8, 7, 6, 5, 4, 3, 2, 0, 0, 0, > 282 9, 8, 7, 6, 5, 4, 3, 2, 0, 0}; > 283 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 284 int _ = 300; > 285 END > 286 /* > 287 CASE(5) > 288 int x_[] = ; > 289 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 290 int y_[] = ; > 291 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 292 int redScore_[] = ; > 293 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 294 int blueScore_[] = ; > 295 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 296 int _ = ; > 297 END > 298 CASE(6) > 299 int x_[] = ; > 300 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 301 int y_[] = ; > 302 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 303 int redScore_[] = ; > 304 vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*r > 305 int blueScore_[] = ; > 306 vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeo > 307 int _ = ; > 308 END > 309 */ > 310 } > 311 // END CUT HERE
Modified lib/geo/ccw.cpp from [81dbefbd30f15e79] to [bec880bc3280bac9].
12 b -= a; c -= a; 12 b -= a; c -= a; 13 if( outer_prod(b,c) > 0 ) return +1; // counter clockwise 13 if( outer_prod(b,c) > 0 ) return +1; // counter clockwise 14 if( outer_prod(b,c) < 0 ) return -1; // clockwise 14 if( outer_prod(b,c) < 0 ) return -1; // clockwise 15 if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line 15 if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line 16 if( norm(b) < norm(c) ) return -2; // [a--b]--c on line 16 if( norm(b) < norm(c) ) return -2; // [a--b]--c on line 17 return 0; // [a--c--b] on line 17 return 0; // [a--c--b] on line 18 } 18 } > 19 > 20 > 21 // intersection of two line segments. > 22 bool cross(CMP p1, CMP p2, CMP P1, CMP P2) { > 23 return ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0; > 24 }