ADDED SRM/TCO14-2A-U/1A.cpp Index: SRM/TCO14-2A-U/1A.cpp ================================================================== --- SRM/TCO14-2A-U/1A.cpp +++ SRM/TCO14-2A-U/1A.cpp @@ -0,0 +1,85 @@ +#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 SixteenBricks { public: + int maximumSurface(vector height) + { + sort(height.begin(), height.end()); + int total = accumulate(height.begin(), height.end(), 0) * 4 + 16; + + total -= height[0] * 4 * 2; + total -= height[1] * 4 * 2; + total -= height[2] * 3 * 2; + total -= height[3] * 3 * 2; + total -= height[4] * 3 * 2; + total -= height[5] * 3 * 2; + total -= height[6] * 2 * 2; + total -= height[7] * 2 * 2; + return total; + } +}; + +// 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(_, SixteenBricks().maximumSurface(height));} +int main(){ + +CASE(0) + int height_[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; + vector height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = 32; +END +CASE(1) + int height_[] = {1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2}; + vector height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = 64; +END +CASE(2) + int height_[] = {77, 78, 58, 34, 30, 20, 8, 71, 37, 74, 21, 45, 39, 16, 4, 59} +; + vector height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = 1798; +END +/* +CASE(3) + int height_[] = ; + vector height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = ; +END +CASE(4) + int height_[] = ; + vector height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO14-2A-U/2B-U.cpp Index: SRM/TCO14-2A-U/2B-U.cpp ================================================================== --- SRM/TCO14-2A-U/2B-U.cpp +++ SRM/TCO14-2A-U/2B-U.cpp @@ -0,0 +1,235 @@ +#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 NarrowPassage { public: + int minDist(int L, vector a, vector b) + { + sortab(a,b); + + int r = 0x3fffffff; + r = min(r, solve_with_partial(L, a, b, 0, "LR", 0)); + r = min(r, solve_with_partial(L, a, b, 0, "RL", 0)); + return r; + } + + void sortab(vector & a, vector & b) + { + const int N = a.size(); + vector> ab; + for(int i=0; i a, vector b, int m, const string& pat, int pati) + { + const int N = a.size(); + int r = 0; + if(m) { + if(pat[pati] == 'L') { + vector idx; + for(int i=0; i idx; + for(int i=m; i& a, const vector& b) + { + const int N = a.size(); + + vector> bad; + set bar; + + for(int i=0; i bar2 = bar; + for(int bb : bar) + for(auto& bi : bad) { + if(bi.first& a, const vector& b, int S, int E) + { + int result = 0; + for(int i=S; i& a, const vector& b, int S, int E) + { + int result = 0; + for(int i=S; i +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(_, NarrowPassage().minDist(L, a, b));} +int main(){ + +CASE(0) + int L = 5; + int a_[] = {1, 2}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {3, 4}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = 4; +END +CASE(1) + int L = 10; + int a_[] = {3, 9}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {8, 6}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = 14; +END +CASE(2) + int L = 265467; + int a_[] = {133548, 103861, 29821, 199848, 92684, 219824, 215859, 62821, 172409, 109235, +38563, 148854, 24742, 174068, 205005, 75922, 87316, 5542, 57484, 40792, +25229, 152216, 21547, 22203, 84712, 231522, 235703, 184895, 100787, 174440, +156904, 84898, 185568, 108732, 260098, 89488, 221604, 104555, 165775, 90444, +81952, 149671, 209674, 22185, 45420, 41928, 16098, 65324, 90870, 35243}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {150289, 135139, 69841, 227226, 177427, 230314, 199175, 81572, 220468, 151049, +40009, 145963, 115246, 252932, 263651, 38434, 120096, 69576, 29789, 115046, +33310, 260771, 5723, 80733, 107864, 142447, 235490, 242149, 124564, 134602, +245962, 7078, 215816, 219864, 190499, 210237, 212894, 142760, 126472, 201935, +119308, 120211, 235235, 19446, 87314, 17286, 61990, 102050, 261812, 257}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = 7148670; +END +CASE(3) + int L = 1000000; + int a_[] = {706292, 756214, 490048, 228791, 567805, 353900, 640393, 562496, 217533, 934149, +938644, 127480, 777134, 999144, 41485, 544051, 417987, 767415, 971662, 959022, +670563, 34065, 518183, 750574, 546576, 207758, 159932, 429345, 670513, 271901, +476062, 392721, 774733, 502586, 915436, 120280, 951729, 699859, 581770, 268966, +79392, 888601, 378829, 350198, 939459, 644983, 605862, 721305, 269232, 137587}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {322468, 673534, 83223, 551733, 341310, 485064, 885415, 927526, 159402, 28144, +441619, 305530, 883149, 413745, 932694, 214862, 677401, 104356, 836580, 300580, +409942, 748444, 744205, 119051, 999286, 462508, 984346, 887773, 856655, 245559, +418763, 840266, 999775, 962927, 779570, 488394, 760591, 326325, 206948, 13999, +285467, 401562, 786209, 169847, 171326, 2901, 296531, 572035, 364920, 939046}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = 45670501; +END +/* +CASE(4) + int L = ; + int a_[] = ; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = ; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = ; +END +CASE(5) + int L = ; + int a_[] = ; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = ; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = ; +END + +*/ +} +// END CUT HERE