Overview
| SHA1 Hash: | 289b0513bab4fff34914cd78364e88267e1623d6 |
|---|---|
| Date: | 2014-02-03 11:41:42 |
| User: | kinaba |
| Comment: | 606 |
| 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/606-U/1A.cpp version [a5b9eb6ef2e80ed6]
> 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 EllysNumberGuessing { public: > 23 int getNumber(vector <int> guesses, vector <int> answers) > 24 { > 25 set<int> cand; > 26 for(int i=0; i<guesses.size(); ++ i) { > 27 set<int> c; > 28 int a = guesses[i]+answers[i]; > 29 if(1<=a && a<=1000000000) c.insert(a); > 30 a = guesses[i]-answers[i]; > 31 if(1<=a && a<=1000000000) c.insert(a); > 32 > 33 if(i==0) > 34 cand = c; > 35 else { > 36 set<int> cc; > 37 set_intersection(cand.begin(), cand.end(), c.beg > 38 cand = cc; > 39 } > 40 } > 41 return cand.size()==1 ? *cand.begin() : cand.size()==2 ? -1 : -2 > 42 } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const int& Expected, const int& Received) { > 54 bool ok = (Expected == Received); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, EllysNumberGuessing().getNumber(guesses, answers > 59 int main(){ > 60 > 61 CASE(0) > 62 int guesses_[] = {600, 594}; > 63 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 64 int answers_[] = {6, 12}; > 65 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 66 int _ = 606; > 67 END > 68 CASE(1) > 69 int guesses_[] = {100, 50, 34, 40}; > 70 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 71 int answers_[] = {58, 8, 8, 2}; > 72 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 73 int _ = 42; > 74 END > 75 CASE(2) > 76 int guesses_[] = {500000, 600000, 700000}; > 77 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 78 int answers_[] = {120013, 220013, 79987}; > 79 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 80 int _ = -2; > 81 END > 82 CASE(3) > 83 int guesses_[] = {500000000}; > 84 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 85 int answers_[] = {133742666}; > 86 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 87 int _ = -1; > 88 END > 89 CASE(4) > 90 int guesses_[] = {76938260, 523164588, 14196746, 296286419, 535893832, > 91 41243148, 364561227, 270003278, 472017422, 367932361, > 92 395758413, 301278456, 186276934, 316343129, 336557549, > 93 52536121, 98343562, 356769915, 89249181, 335191879}; > 94 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 95 int answers_[] = {466274085, 20047757, 529015599, 246925926, 7318513, > 96 501969197, 178651118, 273209067, 71194923, 175279984, > 97 147453932, 241933889, 356935411, 226869216, 206654796, > 98 490676224, 444868783, 186442430, 453963164, 208020466}; > 99 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 100 int _ = 543212345; > 101 END > 102 CASE(5) > 103 int guesses_[] = {42}; > 104 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 105 int answers_[] = {42}; > 106 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 107 int _ = 84; > 108 END > 109 CASE(6) > 110 int guesses_[] = {999900000}; > 111 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 112 int answers_[] = {100001}; > 113 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 114 int _ = 999799999; > 115 END > 116 /* > 117 CASE(7) > 118 int guesses_[] = ; > 119 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 120 int answers_[] = ; > 121 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 122 int _ = ; > 123 END > 124 CASE(8) > 125 int guesses_[] = ; > 126 vector <int> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guess > 127 int answers_[] = ; > 128 vector <int> answers(answers_, answers_+sizeof(answers_)/sizeof(*answe > 129 int _ = ; > 130 END > 131 */ > 132 } > 133 // END CUT HERE
Added SRM/606-U/1B-U.cpp version [ce4d2a0b1b08e640]
> 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 EllysPairing { public: > 23 int getMax(int M, vector <int> count, vector <int> first, vector <int> m > 24 { > 25 int all = accumulate(count.begin(), count.end(), 0); > 26 int max_cnt = maxFreq(M, 0, M, count, first, mult, add); > 27 > 28 if(max_cnt <= all/2) > 29 return all/2; > 30 else > 31 return all - max_cnt; > 32 } > 33 > 34 int maxFreq(unsigned M, int L, int R, > 35 const vector<int>& count, const vector<int>& first, const vector > 36 { > 37 static const int Z = 1<<20; > 38 if(R-L <= Z) { > 39 int freq[Z] = {}; > 40 for(int i=0; i<count.size(); ++i) { > 41 unsigned c = count[i]; > 42 unsigned f = first[i]; > 43 unsigned m = mult[i]; > 44 unsigned a = add[i]; > 45 for(unsigned k=0; k<c; ++k) { > 46 if(L<=f && f<R) freq[f-L]++; > 47 f=(f*m+a)&(M-1); > 48 } > 49 } > 50 return *max_element(freq, freq+(R-L)); > 51 } > 52 > 53 int freq[2] = {}, C = L+(R-L)/2; > 54 for(int i=0; i<count.size(); ++i) { > 55 unsigned c = count[i]; > 56 unsigned f = first[i]; > 57 unsigned m = mult[i]; > 58 unsigned a = add[i]; > 59 for(unsigned k=0; k<c; ++k) { > 60 if(L<=f && f<R) > 61 freq[f<C ? 0 : 1]++; > 62 f=(f*m+a)&(M-1); > 63 } > 64 } > 65 if(freq[0] < freq[1]) > 66 return maxFreq(M, C, R, count, first, mult, add); > 67 else > 68 return maxFreq(M, L, C, count, first, mult, add); > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const int& Expected, const int& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, EllysPairing().getMax(M, count, first, mult, add > 86 int main(){ > 87 > 88 CASE(0) > 89 int M = 16; > 90 int count_[] = {4, 7}; > 91 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 92 int first_[] = {5, 3}; > 93 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 94 int mult_[] = {2, 3}; > 95 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 96 int add_[] = {1, 0}; > 97 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 98 int _ = 5; > 99 END > 100 CASE(1) > 101 int M = 8; > 102 int count_[] = {6, 4, 3}; > 103 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 104 int first_[] = {0, 3, 2}; > 105 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 106 int mult_[] = {3, 7, 5}; > 107 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 108 int add_[] = {0, 3, 2}; > 109 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 110 int _ = 5; > 111 END > 112 CASE(2) > 113 int M = 128; > 114 int count_[] = {42, 13, 666, 17, 1337, 42, 1}; > 115 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 116 int first_[] = {18, 76, 3, 122, 0, 11, 11}; > 117 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 118 int mult_[] = {33, 17, 54, 90, 41, 122, 20}; > 119 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 120 int add_[] = {66, 15, 10, 121, 122, 1, 30}; > 121 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 122 int _ = 1059; > 123 END > 124 CASE(3) > 125 int M = 1048576; > 126 int count_[] = {4242, 42, 9872, 13, 666, 21983, 17, 1337, 42, 1}; > 127 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 128 int first_[] = {19, 18, 76, 42, 3, 112, 0, 11, 11, 12}; > 129 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 130 int mult_[] = {27, 33, 10, 8, 17, 9362, 90, 41, 122, 20}; > 131 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 132 int add_[] = {98, 101, 66, 15, 10, 144, 3, 1, 5, 1}; > 133 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 134 int _ = 16232; > 135 END > 136 CASE(4) > 137 int M = 1073741824; > 138 int count_[] = {894602, 946569, 887230, 856152, 962583, 949356, 904847, > 139 811081, 864078, 809209, 938727, 949135, 892809, 816528, 961237, 979142, 890922} > 140 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 141 int first_[] = {844085078, 898937259, 243490172, 887804102, 187696417, 1 > 142 254936966, 650298774, 982988140, 649258331, 566444626, 201481721, 492943390, 10 > 143 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 144 int mult_[] = {1036482037, 583219072, 819168094, 253755052, 548208982, 4 > 145 860368129, 30334704, 219771462, 733375600, 130839219, 415503960, 294132484, 104 > 146 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 147 int add_[] = {889169006, 604831366, 967292994, 980686280, 844875791, 102 > 148 1049536313, 327207332, 948053446, 271229570, 664579359, 795815285, 842856528, 8 > 149 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 150 int _ = 8971965; > 151 END > 152 CASE(5) > 153 int M = 1073741824; > 154 int count_[] = {227399,73015,235546,945352,318629,384458,55809,766035,53 > 155 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 156 int first_[] = {227399,73015,235546,945352,318629,384458,55809,766035,53 > 157 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 158 int mult_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530 > 159 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 160 int add_[] = {227399,73015,235546,945352,318629,384458,55809,766035,5306 > 161 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 162 int _ = -1; > 163 END > 164 CASE(5) > 165 int M = 1073741824; > 166 int count_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000, > 167 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 168 int first_[] = {775899,967700,946244,694562,767949,840507,668387,555565, > 169 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 170 int mult_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530 > 171 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 172 int add_[] = {227399,73015,235546,945352,318629,384458,55809,766035,5306 > 173 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 174 int _ = -1; > 175 END > 176 /* > 177 CASE(6) > 178 int M = ; > 179 int count_[] = ; > 180 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 181 int first_[] = ; > 182 vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_)); > 183 int mult_[] = ; > 184 vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_)); > 185 int add_[] = ; > 186 vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_)); > 187 int _ = ; > 188 END > 189 */ > 190 } > 191 // END CUT HERE