Overview
| SHA1 Hash: | 15635fe487b0d6b8a8ae270c35390856bc8850e8 |
|---|---|
| Date: | 2019-07-06 12:55:15 |
| User: | kinaba |
| Comment: | TCO192b |
| 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/TCO19-2B-U/1A.cpp version [a6fb42ce604b79df]
> 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 MedianFaking { public: > 23 vector <int> minimize(int F, int M, vector <int> data, int goal) > 24 { > 25 vector<pair<int, int>> VP; > 26 for (int p = 0; p < F; ++p) > 27 for (int m = 0; m < M; ++m) > 28 VP.emplace_back(data[p*M + m], p); > 29 sort(VP.begin(), VP.end()); > 30 > 31 const int N = VP.size(); > 32 const int mid = (N - 1) / 2; > 33 > 34 for (int s = 0; s <= N; ++s) { > 35 if (s == N || VP[s].first >= goal) { > 36 for (int m = s; m <= N; ++m) { > 37 if (m == N || VP[m].first > goal) { > 38 // small goal big > 39 // [0,s)[s,m)[m,N) > 40 if (s <= mid && mid < m) > 41 return{ 0,0 }; > 42 if (s > mid) { > 43 return{ choose(s - mid, > 44 } > 45 if (m <= mid) { > 46 return{ choose(mid - m + > 47 } > 48 return{ -1,-1 }; > 49 } > 50 } > 51 break; > 52 } > 53 } > 54 return{ -1,-1 }; > 55 } > 56 > 57 int choose(int k, const vector<pair<int, int>>& VP) > 58 { > 59 map<int, int> pcmap; > 60 for (auto vp : VP) pcmap[vp.second]++; > 61 vector<int> cs; > 62 for (auto pc : pcmap) cs.emplace_back(pc.second); > 63 sort(cs.rbegin(), cs.rend()); > 64 > 65 int p = 0; > 66 for (auto c: cs) { > 67 ++p; > 68 k -= c; > 69 if (k <= 0) break; > 70 } > 71 return p; > 72 } > 73 }; > 74 > 75 // BEGIN CUT HERE > 76 #include <ctime> > 77 double start_time; string timer() > 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 80 { os << "{ "; > 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 83 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 84 bool ok = (Expected == Received); > 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 86 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, MedianFaking().minimize(F, M, data, goal));} > 89 int main(){ > 90 > 91 CASE(0) > 92 int F = 5; > 93 int M = 5; > 94 int data_[] = {1,2,3,4,5, 10,9,8,7,6, 25,24,23,22,21, 18,16,17,19,20, 11 > 95 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 96 int goal = 8; > 97 int __[] = {1, 5 }; > 98 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 99 END > 100 CASE(1) > 101 int F = 5; > 102 int M = 5; > 103 int data_[] = {1,2,25,24,23, 3,4,22,21,20, 5,6,19,18,17, 7,16,15,14,13, > 104 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 105 int goal = 8; > 106 int __[] = {2, 5 }; > 107 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 108 END > 109 CASE(2) > 110 int F = 1; > 111 int M = 4; > 112 int data_[] = {10, 40, 30, 20}; > 113 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 114 int goal = 20; > 115 int __[] = {0, 0 }; > 116 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 117 END > 118 CASE(3) > 119 int F = 4; > 120 int M = 3; > 121 int data_[] = {3,8,12, 3,8,12, 3,8,12, 8,12,17}; > 122 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 123 int goal = 12; > 124 int __[] = {1, 2 }; > 125 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 126 END > 127 CASE(4) > 128 int F = 5; > 129 int M = 1; > 130 int data_[] = {10, 20, 30, 40, 50}; > 131 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 132 int goal = 23; > 133 int __[] = {1, 1 }; > 134 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 135 END > 136 CASE(5) > 137 int F = 1; > 138 int data_[] = { 2 }; > 139 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 140 int M = data.size()/F; > 141 int goal = 3; > 142 int __[] = { 1,1 }; > 143 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 144 END > 145 /* > 146 CASE(6) > 147 int F = ; > 148 int M = ; > 149 int data_[] = ; > 150 vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_)); > 151 int goal = ; > 152 int __[] = ; > 153 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 154 END > 155 */ > 156 } > 157 // END CUT HERE
Added SRM/TCO19-2B-U/1B.cpp version [48bece87186a64cd]
> 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 DivisorSequences { public: > 23 int longest(int N) > 24 { > 25 int best = 0; > 26 if (N - 1 >= 2) > 27 best = 1 + cnt(N - 1); > 28 best = max(cnt(N), best); > 29 return best; > 30 } > 31 > 32 // The case starting with 2 or above > 33 int cnt(int N) > 34 { > 35 int best = 1; // [N] > 36 > 37 vector<int> divs; > 38 for (int p = 2; p*p <= N && p < N; ++p) > 39 if (N%p == 0) { > 40 divs.push_back(p); > 41 divs.push_back(N/p); > 42 } > 43 > 44 for (int s: divs) > 45 if ((N-s)/s>=2) { > 46 best = max(best, 1 + cnt((N - s) / s)); > 47 } > 48 return best; > 49 } > 50 }; > 51 > 52 // BEGIN CUT HERE > 53 #include <ctime> > 54 double start_time; string timer() > 55 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 56 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 57 { os << "{ "; > 58 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 59 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 60 void verify_case(const int& Expected, const int& Received) { > 61 bool ok = (Expected == Received); > 62 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 63 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 64 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 65 #define END verify_case(_, DivisorSequences().longest(N));} > 66 int main(){ > 67 > 68 CASE(0) > 69 int N = 15; > 70 int _ = 4; > 71 END > 72 CASE(1) > 73 int N = 12; > 74 int _ = 2; > 75 END > 76 CASE(2) > 77 int N = 34; > 78 int _ = 4; > 79 END > 80 CASE(3) > 81 int N = 1000000000; > 82 int _ = -1; > 83 END > 84 CASE(4) > 85 int N = 1 << 30; > 86 int _ = -1; > 87 END > 88 CASE(5) > 89 int N = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23; > 90 int _ = -1; > 91 END > 92 } > 93 // END CUT HERE