ADDED SRM/TCO19-2B-U/1A.cpp Index: SRM/TCO19-2B-U/1A.cpp ================================================================== --- SRM/TCO19-2B-U/1A.cpp +++ SRM/TCO19-2B-U/1A.cpp @@ -0,0 +1,157 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class MedianFaking { public: + vector minimize(int F, int M, vector data, int goal) + { + vector> VP; + for (int p = 0; p < F; ++p) + for (int m = 0; m < M; ++m) + VP.emplace_back(data[p*M + m], p); + sort(VP.begin(), VP.end()); + + const int N = VP.size(); + const int mid = (N - 1) / 2; + + for (int s = 0; s <= N; ++s) { + if (s == N || VP[s].first >= goal) { + for (int m = s; m <= N; ++m) { + if (m == N || VP[m].first > goal) { + // small goal big + // [0,s)[s,m)[m,N) + if (s <= mid && mid < m) + return{ 0,0 }; + if (s > mid) { + return{ choose(s - mid, vector>(VP.begin(), VP.begin() + s)), s - mid }; + } + if (m <= mid) { + return{ choose(mid - m + 1, vector>(VP.begin() + m, VP.end())), mid - m + 1 }; + } + return{ -1,-1 }; + } + } + break; + } + } + return{ -1,-1 }; + } + + int choose(int k, const vector>& VP) + { + map pcmap; + for (auto vp : VP) pcmap[vp.second]++; + vector cs; + for (auto pc : pcmap) cs.emplace_back(pc.second); + sort(cs.rbegin(), cs.rend()); + + int p = 0; + for (auto c: cs) { + ++p; + k -= c; + if (k <= 0) break; + } + return p; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const vector & Expected, const vector & Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, MedianFaking().minimize(F, M, data, goal));} +int main(){ + +CASE(0) + int F = 5; + int M = 5; + int data_[] = {1,2,3,4,5, 10,9,8,7,6, 25,24,23,22,21, 18,16,17,19,20, 11,13,12,14,15}; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int goal = 8; + int __[] = {1, 5 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int F = 5; + int M = 5; + int data_[] = {1,2,25,24,23, 3,4,22,21,20, 5,6,19,18,17, 7,16,15,14,13, 8,12,11,10,9}; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int goal = 8; + int __[] = {2, 5 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + int F = 1; + int M = 4; + int data_[] = {10, 40, 30, 20}; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int goal = 20; + int __[] = {0, 0 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + int F = 4; + int M = 3; + int data_[] = {3,8,12, 3,8,12, 3,8,12, 8,12,17}; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int goal = 12; + int __[] = {1, 2 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + int F = 5; + int M = 1; + int data_[] = {10, 20, 30, 40, 50}; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int goal = 23; + int __[] = {1, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int F = 1; + int data_[] = { 2 }; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int M = data.size()/F; + int goal = 3; + int __[] = { 1,1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(6) + int F = ; + int M = ; + int data_[] = ; + vector data(data_, data_+sizeof(data_)/sizeof(*data_)); + int goal = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE ADDED SRM/TCO19-2B-U/1B.cpp Index: SRM/TCO19-2B-U/1B.cpp ================================================================== --- SRM/TCO19-2B-U/1B.cpp +++ SRM/TCO19-2B-U/1B.cpp @@ -0,0 +1,93 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class DivisorSequences { public: + int longest(int N) + { + int best = 0; + if (N - 1 >= 2) + best = 1 + cnt(N - 1); + best = max(cnt(N), best); + return best; + } + + // The case starting with 2 or above + int cnt(int N) + { + int best = 1; // [N] + + vector divs; + for (int p = 2; p*p <= N && p < N; ++p) + if (N%p == 0) { + divs.push_back(p); + divs.push_back(N/p); + } + + for (int s: divs) + if ((N-s)/s>=2) { + best = max(best, 1 + cnt((N - s) / s)); + } + return best; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, DivisorSequences().longest(N));} +int main(){ + +CASE(0) + int N = 15; + int _ = 4; +END +CASE(1) + int N = 12; + int _ = 2; +END +CASE(2) + int N = 34; + int _ = 4; +END +CASE(3) +int N = 1000000000; +int _ = -1; +END +CASE(4) +int N = 1 << 30; +int _ = -1; +END +CASE(5) +int N = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23; +int _ = -1; +END +} +// END CUT HERE