Overview
| SHA1 Hash: | 3fe379f0296c2393471b8f4c92da1ce721b72887 |
|---|---|
| Date: | 2012-11-30 23:25:43 |
| User: | kinaba |
| Comment: | 561 |
| 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/561-U/1A.cpp version [bf34be831eb65e07]
> 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 ICPCBalloons { public: > 23 static const int INF = 0x3fffffff; > 24 > 25 int minRepaintings(vector <int> balloonCount, string balloonSize, vector > 26 { > 27 const int N = balloonCount.size(); > 28 const int Q = maxAccepted.size(); > 29 > 30 vector<int> M, L; > 31 for(int i=0; i<N; ++i) > 32 (balloonSize[i]=='M' ? M : L).push_back(balloonCount[i]) > 33 > 34 sort(M.rbegin(), M.rend()); > 35 sort(L.rbegin(), L.rend()); > 36 sort(maxAccepted.rbegin(), maxAccepted.rend()); > 37 > 38 int best = INF; > 39 > 40 for(int m=0; m<(1<<Q); ++m) { > 41 vector<int> forM, forL; > 42 for(int i=0; i<Q; ++i) > 43 (m & (1<<i) ? forM : forL).push_back(maxAccepted > 44 best = min(best, cost(M, forM)+cost(L, forL)); > 45 } > 46 return best==INF ? -1 : best; > 47 } > 48 > 49 int cost(const vector<int>& b, const vector<int> q) > 50 { > 51 int more = 0; > 52 int less = 0; > 53 for(int i=0; i<q.size(); ++i) { > 54 int bi = i<b.size() ? b[i] : 0; > 55 if(bi >= q[i]) { > 56 more += bi - q[i]; > 57 } else { > 58 less += q[i] - bi; > 59 } > 60 } > 61 for(int i=q.size(); i<b.size(); ++i) > 62 more += b[i]; > 63 return (more>=less ? less : INF); > 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 int& Expected, const int& 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(_, ICPCBalloons().minRepaintings(balloonCount, ball > 81 int main(){ > 82 > 83 CASE(0) > 84 int balloonCount_[] = {100}; > 85 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 86 string balloonSize = "L"; > 87 int maxAccepted_[] = {1,2,3,4,5}; > 88 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 89 int _ = 10; > 90 END > 91 CASE(1) > 92 int balloonCount_[] = {100}; > 93 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 94 string balloonSize = "M"; > 95 int maxAccepted_[] = {10,20,30,40,50}; > 96 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 97 int _ = -1; > 98 END > 99 CASE(2) > 100 int balloonCount_[] = {5,6,1,5,6,1,5,6,1}; > 101 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 102 string balloonSize = "MLMMLMMLM"; > 103 int maxAccepted_[] = {7,7,4,4,7,7}; > 104 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 105 int _ = 6; > 106 END > 107 CASE(3) > 108 int balloonCount_[] = {100,100}; > 109 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 110 string balloonSize = "ML"; > 111 int maxAccepted_[] = {50,51,51}; > 112 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 113 int _ = -1; > 114 END > 115 CASE(4) > 116 int balloonCount_[] = {8,5,1,4,1,1,3,1,3,3,5,4,5,6,9}; > 117 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 118 string balloonSize = "MMMLLLMMLLMLMLM"; > 119 int maxAccepted_[] = {3,5,3,3,5,6,4,6,4,2,3,7,1,5,2}; > 120 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 121 int _ = 5; > 122 END > 123 CASE(5) > 124 int balloonCount_[] = {1,18,4,7,19,7,7,1,4,8,10,5,14,13,8,22,6,3,13,5,3, > 125 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 126 string balloonSize = "LLMLLLLMLLLLLLLLLLLLMLLLLLLLLLLMMLMLLLMLLLLLLLLMLL > 127 int maxAccepted_[] = {44,59,29,53,16,23,13,14,29,42,13,15,66,4,47}; > 128 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 129 int _ = 210; > 130 END > 131 /* > 132 CASE(6) > 133 int balloonCount_[] = ; > 134 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 135 string balloonSize = ; > 136 int maxAccepted_[] = ; > 137 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 138 int _ = ; > 139 END > 140 CASE(7) > 141 int balloonCount_[] = ; > 142 vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonC > 143 string balloonSize = ; > 144 int maxAccepted_[] = ; > 145 vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted > 146 int _ = ; > 147 END > 148 */ > 149 } > 150 // END CUT HERE
Added SRM/561-U/1B-U.cpp version [4f1638dcf4f1be51]
> 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 CirclesGame { public: > 23 string whoCanWin(vector <int> x, vector <int> y, vector <int> r) > 24 { > 25 vector< pair<int, pair<int,int> > > xyr; > 26 const int N = x.size(); > 27 for(int i=0; i<N; ++i) > 28 xyr.push_back(make_pair(r[i], make_pair(x[i],y[i]))); > 29 sort(xyr.begin(), xyr.end()); > 30 > 31 vector<int> parent(N, -1); > 32 for(int i=0; i<N; ++i) { > 33 for(int k=i+1; k<N; ++k) { > 34 int r1 = xyr[i].first; > 35 int x1 = xyr[i].second.first; > 36 int y1 = xyr[i].second.second; > 37 int r2 = xyr[k].first; > 38 int x2 = xyr[k].second.first; > 39 int y2 = xyr[k].second.second; > 40 if( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) < r2*r2 ) > 41 {parent[i] = k; break;} > 42 } > 43 } > 44 return solve(N, parent) ? "Bob" : "Alice"; > 45 } > 46 > 47 bool solve(int N, const vector<int>& p) > 48 { > 49 vector<int> r; > 50 vector< vector<int> > c(N); > 51 for(int i=0; i<N; ++i) > 52 if(p[i] == -1) > 53 r.push_back(i); > 54 else > 55 c[p[i]].push_back(i); > 56 > 57 memo.assign(N, -1); > 58 > 59 int XOR = 0; > 60 for(int i=0; i<r.size(); ++i) { > 61 int g = grundy(c, r[i]); > 62 XOR ^= g; > 63 } > 64 return XOR == 0; > 65 } > 66 > 67 vector<int> memo; > 68 int grundy(const vector< vector<int> >& ch, int v) > 69 { > 70 if(memo[v]!=-1) > 71 return memo[v]; > 72 > 73 vector<int> next; > 74 rec(ch, v, 0, next); > 75 return memo[v] = mex(next); > 76 } > 77 > 78 void rec(const vector< vector<int> >& ch, int v, int XOR_acc, vector<int > 79 { > 80 int XOR = XOR_acc; > 81 for(int i=0; i<ch[v].size(); ++i) > 82 XOR ^= grundy(ch, ch[v][i]); > 83 > 84 // cut here. > 85 next.push_back(XOR); > 86 // go below. > 87 for(int i=0; i<ch[v].size(); ++i) > 88 rec(ch, ch[v][i], XOR^grundy(ch, ch[v][i]), next); > 89 } > 90 > 91 int mex(vector<int>& next) > 92 { > 93 sort(next.begin(), next.end()); > 94 for(int k=0; k<next.size(); ++k) > 95 if( k != next[k] ) > 96 return k; > 97 return next.size(); > 98 } > 99 }; > 100 > 101 // BEGIN CUT HERE > 102 #include <ctime> > 103 double start_time; string timer() > 104 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 105 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 106 { os << "{ "; > 107 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 108 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 109 void verify_case(const string& Expected, const string& Received) { > 110 bool ok = (Expected == Received); > 111 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 113 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 114 #define END verify_case(_, CirclesGame().whoCanWin(x, y, r));} > 115 int main(){ > 116 > 117 CASE(0) > 118 int x_[] = {0}; > 119 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 120 int y_[] = {0}; > 121 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 122 int r_[] = {1}; > 123 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 124 string _ = "Alice"; > 125 END > 126 CASE(1) > 127 int x_[] = {0, 3}; > 128 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 129 int y_[] = {0, 0}; > 130 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 131 int r_[] = {1, 1}; > 132 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 133 string _ = "Bob"; > 134 END > 135 CASE(2) > 136 int x_[] = {0, 0, 5}; > 137 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 138 int y_[] = {0, 0, 0}; > 139 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 140 int r_[] = {1, 2, 1}; > 141 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 142 string _ = "Alice"; > 143 END > 144 CASE(3) > 145 int x_[] = {0, 0, 0, 10, 10, 20}; > 146 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 147 int y_[] = {0, 0, 0, 0, 0, 0}; > 148 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 149 int r_[] = {1, 2, 3, 1, 2, 1}; > 150 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 151 string _ = "Bob"; > 152 END > 153 CASE(4) > 154 int x_[] = {10,20,30,40,50,60,70,80}; > 155 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 156 int y_[] = {8,7,6,5,4,3,2,1}; > 157 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 158 int r_[] = {2,2,2,2,2,2,2,2}; > 159 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 160 string _ = "Bob"; > 161 END > 162 CASE(5) > 163 int x_[] = {0, 3, 6, 9, 12, -4747, -4777}; > 164 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 165 int y_[] = {-5858, -5858, -5858, -5858, -5858, 777, 777}; > 166 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 167 int r_[] = {58, 1, 1, 1, 1, 44, 8}; > 168 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 169 string _ = "Bob"; > 170 END > 171 CASE(6) > 172 int x_[] = {5202, 5699, -7433, 5068, -9483, -684, -6593, 5108, -7813, 68 > 173 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 174 int y_[] = {8728, -7407, 4338, -8414, 7652, -3705, -984, 5976, -9180, -9 > 175 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 176 int r_[] = {4196, 9303, 7152, 5875, 2943, 788, 502, 416, 1958, 3174, 182 > 177 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 178 string _ = "Alice"; > 179 END > 180 /* > 181 CASE(7) > 182 int x_[] = ; > 183 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 184 int y_[] = ; > 185 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 186 int r_[] = ; > 187 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 188 string _ = ; > 189 END > 190 CASE(8) > 191 int x_[] = ; > 192 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 193 int y_[] = ; > 194 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 195 int r_[] = ; > 196 vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); > 197 string _ = ; > 198 END > 199 */ > 200 } > 201 // END CUT HERE