Overview
| SHA1 Hash: | aca31be9a5f3302e6b374ba8bd62d8f267f30465 |
|---|---|
| Date: | 2011-12-24 01:28:24 |
| User: | kinaba |
| Comment: | 527 |
| 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/526-U/2A.cpp version [aa83e3a5e10e2fe4]
> 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 CheatingQuiz { public: > 29 vector <int> howMany(string answers) > 30 { > 31 int N = answers.size(); > 32 vector<int> re; > 33 int A = count(answers.begin(), answers.end(), 'A'); > 34 int B = count(answers.begin(), answers.end(), 'B'); > 35 int C = count(answers.begin(), answers.end(), 'C'); > 36 for(int i=0; i<N; ++i) { > 37 re.push_back(!!A + !!B + !!C); > 38 (answers[i]=='A' ? A : answers[i]=='B' ? B : C)--; > 39 } > 40 return re; > 41 } > 42 }; > 43 > 44 // BEGIN CUT HERE > 45 #include <ctime> > 46 double start_time; string timer() > 47 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 48 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 49 { os << "{ "; > 50 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 51 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 52 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 53 bool ok = (Expected == Received); > 54 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 55 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 56 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 57 #define END verify_case(_, CheatingQuiz().howMany(answers));} > 58 int main(){ > 59 > 60 CASE(0) > 61 string answers = "AAAAA"; > 62 int __[] = {1, 1, 1, 1, 1 }; > 63 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 64 END > 65 CASE(1) > 66 string answers = "AAABBB"; > 67 int __[] = {2, 2, 2, 1, 1, 1 }; > 68 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 69 END > 70 CASE(2) > 71 string answers = "CAAAAAC"; > 72 int __[] = {2, 2, 2, 2, 2, 2, 1 }; > 73 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 74 END > 75 CASE(3) > 76 string answers = "BBCA"; > 77 int __[] = {3, 3, 2, 1 }; > 78 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 79 END > 80 CASE(4) > 81 string answers = "BACACABCBBBBCAAAAACCCABBCAA"; > 82 int __[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, > 83 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 84 END > 85 /* > 86 CASE(5) > 87 string answers = ; > 88 int __[] = ; > 89 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 90 END > 91 CASE(6) > 92 string answers = ; > 93 int __[] = ; > 94 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 95 END > 96 */ > 97 } > 98 // END CUT HERE
Added SRM/527-U/1A.cpp version [e86c37863d2b6878]
> 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 P8XGraphBuilder { public: > 29 int solve(vector <int> scores) > 30 { > 31 scores.insert(scores.begin(), 9999999); > 32 const int N = scores.size(); > 33 > 34 int best = 0; > 35 for(int leaves=1; leaves<N; ++leaves) > 36 best = max(best, scores[1]*leaves + calc(leaves, N-leave > 37 return best; > 38 } > 39 > 40 map<pair<int,int>,int> memo; > 41 int calc(int leaves, int nodes, const vector<int>& scores) > 42 { > 43 if( nodes == 1 ) > 44 return scores[leaves]; > 45 > 46 pair<int,int> key(leaves, nodes); > 47 if( memo.count(key) ) > 48 return memo[key]; > 49 > 50 int best = 0; > 51 for(int k=1; k<=leaves; ++k) > 52 best = max(best, scores[k+1] + calc(leaves-k+1, nodes-1, > 53 return memo[key] = best; > 54 } > 55 }; > 56 > 57 // BEGIN CUT HERE > 58 #include <ctime> > 59 double start_time; string timer() > 60 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 61 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 62 { os << "{ "; > 63 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 64 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 65 void verify_case(const int& Expected, const int& Received) { > 66 bool ok = (Expected == Received); > 67 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 68 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 69 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 70 #define END verify_case(_, P8XGraphBuilder().solve(scores));} > 71 int main(){ > 72 > 73 CASE(0) > 74 int scores_[] = {1, 3, 0}; > 75 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 76 int _ = 8; > 77 END > 78 CASE(1) > 79 int scores_[] = {0, 0, 0, 10}; > 80 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 81 int _ = 10; > 82 END > 83 CASE(2) > 84 int scores_[] = {1, 2, 3, 4, 5, 6}; > 85 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 86 int _ = 12; > 87 END > 88 CASE(3) > 89 int scores_[] = {5, 0, 0}; > 90 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 91 int _ = 15; > 92 END > 93 CASE(4) > 94 int scores_[] = {1, 3, 2, 5, 3, 7, 5}; > 95 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 96 int _ = 20; > 97 END > 98 CASE(5) > 99 int scores_[] = {1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10, > 100 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 101 int _ = -1; > 102 END > 103 CASE(6) > 104 int scores_[] = {2}; > 105 vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)) > 106 int _ = 4; > 107 END > 108 > 109 } > 110 // END CUT HERE
Added SRM/527-U/1B.cpp version [9446f824184a311c]
> 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 typedef int vert; > 29 typedef vert edge; > 30 typedef vector<edge> edges; > 31 typedef vector<edges> graph; > 32 > 33 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) > 34 { > 35 for(int i=0; i<G[v].size(); ++i) { > 36 vert u = G[v][i]; > 37 if( visited[u] ) continue; > 38 visited[u] = true; > 39 > 40 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) > 41 { matchTo[v]=u, matchTo[u]=v; return true; } > 42 } > 43 return false; > 44 } > 45 > 46 template<int NV> > 47 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right > 48 // only left->right edges are used during computation > 49 { > 50 vector<vert> matchTo(G.size(), -1); > 51 int ans = 0; > 52 for(vert v=0; v<L; ++v) { > 53 bool visited[NV] = {}; > 54 if( augment(G, v, matchTo, visited) ) > 55 ++ans; > 56 } > 57 return ans; > 58 } > 59 > 60 class P8XMatrixRecovery { public: > 61 int H, W; > 62 vector <string> solve(vector <string> rows, vector <string> columns) > 63 { > 64 H = rows.size(); > 65 W = rows[0].size(); > 66 for(int y=0; y<H; ++y) > 67 for(int x=0; x<W; ++x) > 68 if( rows[y][x] == '?' ) { > 69 rows[y][x] = '0'; > 70 if( !can(rows, columns) ) > 71 rows[y][x] = '1'; > 72 } > 73 return rows; > 74 } > 75 > 76 bool can(const vector<string>& rows, const vector<string>& columns) > 77 { > 78 graph G(W*2); > 79 for(int x1=0; x1<W; ++x1) { > 80 string left; > 81 for(int y=0; y<H; ++y) > 82 left += rows[y][x1]; > 83 for(int x2=0; x2<W; ++x2) > 84 if( match(left, columns[x2]) ) > 85 G[x1].push_back(x2+W); > 86 } > 87 return biMatch<60>(G, W) == W; > 88 } > 89 > 90 bool match( const string& l, const string& r ) > 91 { > 92 for(int i=0; i<l.size(); ++i) > 93 if( l[i]!=r[i] && l[i]!='?' && r[i]!='?' ) > 94 return false; > 95 return true; > 96 } > 97 }; > 98 > 99 // BEGIN CUT HERE > 100 #include <ctime> > 101 double start_time; string timer() > 102 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 103 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 104 { os << "{ "; > 105 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 106 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 107 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 108 bool ok = (Expected == Received); > 109 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 110 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 111 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 112 #define END verify_case(_, P8XMatrixRecovery().solve(rows, columns));} > 113 int main(){ > 114 > 115 CASE(0) > 116 string rows_[] = {"10?" > 117 ,"?11"}; > 118 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 119 string columns_[] = {"01" > 120 ,"10" > 121 ,"1?"} > 122 ; > 123 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 124 string __[] = {"101", "011" }; > 125 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 126 END > 127 CASE(1) > 128 string rows_[] = {"0" > 129 ,"?" > 130 ,"1"}; > 131 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 132 string columns_[] = {"0?1"}; > 133 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 134 string __[] = {"0", "0", "1" }; > 135 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 136 END > 137 CASE(2) > 138 string rows_[] = {"10" > 139 ,"01"}; > 140 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 141 string columns_[] = {"10" > 142 ,"01"}; > 143 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 144 string __[] = {"10", "01" }; > 145 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 146 END > 147 CASE(3) > 148 string rows_[] = {"??0" > 149 ,"11?" > 150 ,"?01" > 151 ,"1?1"}; > 152 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 153 string columns_[] = {"1???" > 154 ,"?111" > 155 ,"0?1?"}; > 156 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 157 string __[] = {"010", "110", "101", "101" }; > 158 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 159 END > 160 CASE(4) > 161 string rows_[] = { > 162 "??????????????????????????????", > 163 "??????????????????????????????", > 164 "??????????????????????????????", > 165 "??????????????????????????????", > 166 "??????????????????????????????", > 167 "??????????????????????????????", > 168 "??????????????????????????????", > 169 "??????????????????????????????", > 170 "??????????????????????????????", > 171 "??????????????????????????????", > 172 "??????????????????????????????", > 173 "??????????????????????????????", > 174 "??????????????????????????????", > 175 "??????????????????????????????", > 176 "??????????????????????????????", > 177 "??????????????????????????????", > 178 "??????????????????????????????", > 179 "??????????????????????????????", > 180 "??????????????????????????????", > 181 "??????????????????????????????", > 182 "??????????????????????????????", > 183 "??????????????????????????????", > 184 "??????????????????????????????", > 185 "??????????????????????????????", > 186 "??????????????????????????????", > 187 "??????????????????????????????", > 188 "??????????????????????????????", > 189 "??????????????????????????????", > 190 "??????????????????????????????", > 191 "??????????????????????????????", > 192 }; > 193 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 194 string columns_[] = { > 195 "??????????????????????????????", > 196 "??????????????????????????????", > 197 "??????????????????????????????", > 198 "??????????????????????????????", > 199 "??????????????????????????????", > 200 "??????????????????????????????", > 201 "??????????????????????????????", > 202 "??????????????????????????????", > 203 "??????????????????????????????", > 204 "??????????????????????????????", > 205 "??????????????????????????????", > 206 "??????????????????????????????", > 207 "??????????????????????????????", > 208 "??????????????????????????????", > 209 "??????????????????????????????", > 210 "??????????????????????????????", > 211 "??????????????????????????????", > 212 "??????????????????????????????", > 213 "??????????????????????????????", > 214 "??????????????????????????????", > 215 "??????????????????????????????", > 216 "??????????????????????????????", > 217 "??????????????????????????????", > 218 "??????????????????????????????", > 219 "??????????????????????????????", > 220 "??????????????????????????????", > 221 "??????????????????????????????", > 222 "??????????????????????????????", > 223 "??????????????????????????????", > 224 "??????????????????????????????", > 225 }; > 226 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 227 string __[] = {"?"}; > 228 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 229 END > 230 CASE(5) > 231 string rows_[] = {"?"}; > 232 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 233 string columns_[] = {"?"}; > 234 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 235 string __[] = {"0"}; > 236 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 237 END > 238 CASE(6) > 239 string rows_[] = {"??","??"}; > 240 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 241 string columns_[] = {"00","11"}; > 242 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 243 string __[] = {"01","01"}; > 244 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 245 END > 246 CASE(7) > 247 string rows_[] = {"0??", "?0?"}; > 248 vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); > 249 string columns_[] = {"01", "00", "10"}; > 250 vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*co > 251 string __[] = {"001", "100"}; > 252 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 253 END > 254 > 255 } > 256 // END CUT HERE
Added SRM/527-U/2A.cpp version [395d0c02f1fc9461]
> 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 P8XMatrixTransformation { public: > 29 string solve(vector <string> original, vector <string> target) > 30 { > 31 int so = 0, st = 0; > 32 for(int y=0; y<original.size(); ++y) { > 33 so += accumulate(original[y].begin(), original[y].end(), > 34 st += accumulate(target[y].begin(), target[y].end(), 0); > 35 } > 36 return so==st ? "YES" : "NO"; > 37 } > 38 }; > 39 > 40 // BEGIN CUT HERE > 41 #include <ctime> > 42 double start_time; string timer() > 43 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 44 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 45 { os << "{ "; > 46 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 47 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 48 void verify_case(const string& Expected, const string& Received) { > 49 bool ok = (Expected == Received); > 50 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 51 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 52 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 53 #define END verify_case(_, P8XMatrixTransformation().solve(original, target > 54 int main(){ > 55 > 56 CASE(0) > 57 string original_[] = {"01" > 58 ,"11"}; > 59 vector <string> original(original_, original_+sizeof(original_)/sizeof > 60 string target_[] = {"11" > 61 ,"10"}; > 62 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 63 string _ = "YES"; > 64 END > 65 CASE(1) > 66 string original_[] = {"0111" > 67 ,"0011"}; > 68 vector <string> original(original_, original_+sizeof(original_)/sizeof > 69 string target_[] = {"1011" > 70 ,"1100"}; > 71 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 72 string _ = "YES"; > 73 END > 74 CASE(2) > 75 string original_[] = {"0"}; > 76 vector <string> original(original_, original_+sizeof(original_)/sizeof > 77 string target_[] = {"1"}; > 78 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 79 string _ = "NO"; > 80 END > 81 CASE(3) > 82 string original_[] = {"1111" > 83 ,"1111" > 84 ,"0000" > 85 ,"0000"}; > 86 vector <string> original(original_, original_+sizeof(original_)/sizeof > 87 string target_[] = {"1111" > 88 ,"1111" > 89 ,"0000" > 90 ,"0000"}; > 91 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 92 string _ = "YES"; > 93 END > 94 CASE(4) > 95 string original_[] = {"0110" > 96 ,"1001" > 97 ,"0110"}; > 98 vector <string> original(original_, original_+sizeof(original_)/sizeof > 99 string target_[] = {"1111" > 100 ,"0110" > 101 ,"0000"}; > 102 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 103 string _ = "YES"; > 104 END > 105 CASE(5) > 106 string original_[] = {"0000" > 107 ,"1111" > 108 ,"0000"}; > 109 vector <string> original(original_, original_+sizeof(original_)/sizeof > 110 string target_[] = {"1111" > 111 ,"0000" > 112 ,"1111"}; > 113 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 114 string _ = "NO"; > 115 END > 116 /* > 117 CASE(6) > 118 string original_[] = ; > 119 vector <string> original(original_, original_+sizeof(original_)/sizeof > 120 string target_[] = ; > 121 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 122 string _ = ; > 123 END > 124 CASE(7) > 125 string original_[] = ; > 126 vector <string> original(original_, original_+sizeof(original_)/sizeof > 127 string target_[] = ; > 128 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target > 129 string _ = ; > 130 END > 131 */ > 132 } > 133 // END CUT HERE
Added SRM/527-U/2C.cpp version [8a1cb626f49403d6]
> 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 P8XCoinChangeAnother { public: > 29 vector<long long> solve(int N, long long coins_sum, long long coins_coun > 30 { > 31 vector<LL> result; > 32 for(int i=0; i<N; ++i) { > 33 LL tick = i==N-1 ? coins_sum>>i : ((1LL<<i)&coins_sum ? > 34 result.push_back( tick ); > 35 coins_count -= tick; > 36 } > 37 if( coins_count < 0 ) > 38 return vector<LL>(); > 39 > 40 for(int i=N-1; i>0; --i) { > 41 if( coins_count == 0 ) > 42 return result; > 43 else { > 44 LL& me = result[i]; > 45 LL dec = min(me, coins_count); > 46 me -= dec; > 47 result[i-1] += dec*2; > 48 coins_count -= dec; > 49 } > 50 } > 51 return coins_count == 0 ? result : vector<LL>(); > 52 } > 53 }; > 54 > 55 // BEGIN CUT HERE > 56 #include <ctime> > 57 double start_time; string timer() > 58 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 59 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 60 { os << "{ "; > 61 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 62 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 63 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 64 bool ok = (Expected == Received); > 65 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 66 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 67 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 68 #define END verify_case(_, P8XCoinChangeAnother().solve(N, coins_sum, coins > 69 int main(){ > 70 > 71 CASE(0) > 72 int N = 2; > 73 long long coins_sum = 4LL; > 74 long long coins_count = 3LL; > 75 long long __[] = {2, 1 }; > 76 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 77 END > 78 CASE(1) > 79 int N = 3; > 80 long long coins_sum = 6LL; > 81 long long coins_count = 3LL; > 82 long long __[] = {0, 3, 0 }; > 83 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 84 END > 85 CASE(2) > 86 int N = 2; > 87 long long coins_sum = 8LL; > 88 long long coins_count = 1LL; > 89 vector<long long> _; > 90 END > 91 CASE(3) > 92 int N = 1; > 93 long long coins_sum = 10000000000LL; > 94 long long coins_count = 10000000000LL; > 95 long long __[] = {10000000000 }; > 96 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 97 END > 98 /* > 99 CASE(4) > 100 int N = ; > 101 long long coins_sum = LL; > 102 long long coins_count = LL; > 103 long long __[] = ; > 104 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(5) > 107 int N = ; > 108 long long coins_sum = LL; > 109 long long coins_count = LL; > 110 long long __[] = ; > 111 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 112 END > 113 */ > 114 } > 115 // END CUT HERE