Overview
| SHA1 Hash: | 2573eaa21602a8557485a16d8a3a351e5e3b784c |
|---|---|
| Date: | 2013-03-25 15:04:21 |
| User: | kinaba |
| Comment: | 573 |
| 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/573-U/1A-U.cpp version [1662779681209416]
> 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 TeamContest { public: > 23 int worstRank(vector <int> s) > 24 { > 25 int N = s.size()/3; > 26 int us = str(s[0], s[1], s[2]); > 27 sort(s.begin()+3, s.end()); > 28 int L = 0; // |<=us| <= 0 is impossible > 29 int R = N-1; // |<=us| <= N-1 is possible > 30 while(R-L>1) > 31 { > 32 int C = (L+R)/2; > 33 (possible(us, C, s) ? R : L) = C; > 34 } > 35 return N-R; > 36 } > 37 > 38 int str(int a, int b, int c) > 39 { > 40 return max(max(a,b),c) + min(min(a,b),c); > 41 } > 42 > 43 // |<=us| <= UB possible? > 44 bool possible(int us, int UB, const vector<int>& s) > 45 { > 46 int si = 3; > 47 > 48 // from weak teams > 49 while(UB > 0) { > 50 if(si==s.size()) > 51 return true; > 52 si += 3; > 53 --UB; > 54 } > 55 > 56 if(si==s.size()) > 57 return true; // no more team left > 58 > 59 // can we make every other teams stronger than ourselves? > 60 vector<int> ss(s.begin()+si, s.end()); > 61 while(!ss.empty()) > 62 if(!takeOut(us, ss)) > 63 return false; > 64 return true; > 65 } > 66 > 67 bool takeOut(int us, vector<int>& s) > 68 { > 69 int a = s[0]; > 70 s.erase(s.begin()); > 71 int b = s[0]; > 72 s.erase(s.begin()); > 73 for(int i=0; i<s.size(); ++i) { > 74 int c = s[i]; > 75 if(str(a,b,c) > us) { > 76 s.erase(s.begin()+i); > 77 return true; > 78 } > 79 } > 80 return false; > 81 } > 82 }; > 83 > 84 // BEGIN CUT HERE > 85 #include <ctime> > 86 double start_time; string timer() > 87 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 88 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 89 { os << "{ "; > 90 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 91 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 92 void verify_case(const int& Expected, const int& Received) { > 93 bool ok = (Expected == Received); > 94 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 95 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 96 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 97 #define END verify_case(_, TeamContest().worstRank(strength));} > 98 int main(){ > 99 > 100 CASE(0) > 101 int strength_[] = {5, 7, 3, 5, 7, 3, 5, 7, 3}; > 102 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 103 int _ = 2; > 104 END > 105 CASE(1) > 106 int strength_[] = {5, 7, 3} > 107 ; > 108 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 109 int _ = 1; > 110 END > 111 CASE(2) > 112 int strength_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; > 113 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 114 int _ = 1; > 115 END > 116 CASE(3) > 117 int strength_[] = {3,9,4,6,2,6,1,6,9,1,4,1,3,8,5} > 118 ; > 119 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 120 int _ = 3; > 121 END > 122 CASE(4) > 123 int strength_[] = {53,47,88,79,99,75,28,54,65,14,22,13,11,31,43} > 124 ; > 125 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 126 int _ = 3; > 127 END > 128 CASE(5) > 129 int strength_[] = {2,2,2,1,1,1,1,1,5}; > 130 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 131 int _ = 2; > 132 END > 133 /* > 134 CASE(6) > 135 int strength_[] = ; > 136 vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*s > 137 int _ = ; > 138 END > 139 */ > 140 } > 141 // END CUT HERE
Added SRM/573-U/1B.cpp version [58e82fd59ea2f53d]
> 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 SkiResorts { public: > 23 long long minCost(vector <string> road, vector <int> altitude) > 24 { > 25 typedef int Vert; > 26 typedef int Alt; > 27 typedef pair<Vert,Alt> State; > 28 typedef LL Cost; > 29 typedef pair<Cost,State> Edge; > 30 const int N = altitude.size(); > 31 > 32 priority_queue< Edge, vector<Edge>, greater<Edge> > Q; > 33 set<State> V; > 34 for(int i=0; i<N; ++i) { > 35 State init(0, altitude[i]); > 36 Q.push( Edge(abs(altitude[i]-altitude[0]), init) ); > 37 } > 38 while( !Q.empty() ) { > 39 Cost c = Q.top().first; > 40 State s = Q.top().second; > 41 Vert v = s.first; > 42 Alt vh = s.second; > 43 Q.pop(); > 44 if( V.count(s) ) > 45 continue; > 46 V.insert(s); > 47 if( v == N-1 ) > 48 return c; > 49 > 50 for(Vert u=0; u<N; ++u) if(road[v][u] =='Y') { > 51 Alt uh = altitude[u]; > 52 for(int i=0; i<N; ++i) { > 53 Alt ch = altitude[i]; > 54 if( ch <= vh ) { > 55 Cost cc = c + abs(ch-uh); > 56 State ss(u, ch); > 57 if(!V.count(ss)) > 58 Q.push(Edge(cc,ss)); > 59 } > 60 } > 61 } > 62 } > 63 return -1; > 64 } > 65 }; > 66 > 67 // BEGIN CUT HERE > 68 #include <ctime> > 69 double start_time; string timer() > 70 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 71 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 72 { os << "{ "; > 73 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 74 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 75 void verify_case(const long long& Expected, const long long& Received) { > 76 bool ok = (Expected == Received); > 77 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 78 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 79 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 80 #define END verify_case(_, SkiResorts().minCost(road, altitude));} > 81 int main(){ > 82 CASE(0) > 83 string road_[] = {"NYN", > 84 "YNY", > 85 "NYN"}; > 86 vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 87 int altitude_[] = {30, 20, 10}; > 88 vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*a > 89 long long _ = 0LL; > 90 END > 91 CASE(1) > 92 string road_[] = {"NY", > 93 "YN"}; > 94 vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 95 int altitude_[] = {10, 20}; > 96 vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*a > 97 long long _ = 10LL; > 98 END > 99 CASE(2) > 100 string road_[] = {"NYN", > 101 "YNN", > 102 "NNN"}; > 103 vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 104 int altitude_[] = {573, 573, 573}; > 105 vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*a > 106 long long _ = -1LL; > 107 END > 108 CASE(3) > 109 string road_[] = {"NNYNNYYYNN", > 110 "NNNNYNYNNN", > 111 "YNNNNYYNNN", > 112 "NNNNNNYNYY", > 113 "NYNNNNNNYY", > 114 "YNYNNNNYNN", > 115 "YYYYNNNYNN", > 116 "YNNNNYYNNN", > 117 "NNNYYNNNNN", > 118 "NNNYYNNNNN"}; > 119 vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 120 int altitude_[] = {7, 4, 13, 2, 8, 1, 8, 15, 5, 15}; > 121 vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*a > 122 long long _ = 12LL; > 123 END > 124 CASE(4) > 125 string road_[] = { > 126 "NYNNNNNN", > 127 "YNYNNNNN", > 128 "NYNYNNNN", > 129 "NNYNYNNN", > 130 "NNNYNYNN", > 131 "NNNNYNYN", > 132 "NNNNNYNY", > 133 "NNNNNNYN" > 134 }; > 135 vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 136 int altitude_[] = { > 137 1,2,3,3,3,3,3,3 > 138 }; > 139 vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*a > 140 long long _ = 3LL; > 141 END > 142 /* > 143 CASE(5) > 144 string road_[] = ; > 145 vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 146 int altitude_[] = ; > 147 vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*a > 148 long long _ = LL; > 149 END > 150 */ > 151 } > 152 // END CUT HERE