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 <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +#include <tuple> +using namespace std; +typedef long long LL; +typedef complex<double> CMP; + +class SixteenBricks { public: + int maximumSurface(vector <int> 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 <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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 <int> 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 <int> 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 <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = 1798; +END +/* +CASE(3) + int height_[] = ; + vector <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); + int _ = ; +END +CASE(4) + int height_[] = ; + vector <int> 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 <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +#include <tuple> +using namespace std; +typedef long long LL; +typedef complex<double> CMP; + +class NarrowPassage { public: + int minDist(int L, vector <int> a, vector <int> 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 <int>& a, vector <int>& b) + { + const int N = a.size(); + vector<pair<int,int>> ab; + for(int i=0; i<N; ++i) + ab.emplace_back(a[i], b[i]); + sort(ab.begin(), ab.end()); + for(int i=0; i<N; ++i) { + a[i] = ab[i].first; + b[i] = ab[i].second; + } + } + + int solve_with_partial(int L, vector<int> a, vector<int> b, int m, const string& pat, int pati) + { + const int N = a.size(); + int r = 0; + if(m) { + if(pat[pati] == 'L') { + vector<int> idx; + for(int i=0; i<m; ++i) + idx.push_back(i); + sort(idx.begin(), idx.end(), [&](int i, int k){ + return b[i]<b[k]; + }); + + for(int ii=0; ii<idx.size(); ++ii) { + int i = idx[ii]; + int np = ii+1; + r += a[i] + np; + a[i] = np; + } + } else { + vector<int> idx; + for(int i=m; i<N; ++i) + idx.push_back(i); + sort(idx.begin(), idx.end(), [&](int i, int k){ + return b[i]<b[k]; + }); + + for(int ii=0; ii<idx.size(); ++ii) { + int i = idx[ii]; + int np = L-(idx.size()-ii); + r += abs(L-a[i]) + abs(L-np); + a[i] = np; + } + } + sortab(a, b); + } + + if(pati == pat.size()) + return r + solve(L, a, b); + + int best = 0x3fffffff; + for(int mm=0; mm<N; ++mm) + best = min(best, r + solve_with_partial(L, a, b, mm, pat, pati+1)); + return best; + } + + int solve(int L, const vector<int>& a, const vector<int>& b) + { + const int N = a.size(); + + vector<pair<int,int>> bad; + set<int> bar; + + for(int i=0; i<N; ++i) + for(int k=i+1; k<N; ++k) + if(!(b[i]<b[k])) { + bad.emplace_back(i, k+1); + bar.insert(i); + bar.insert(k+1); + } + + { + set<int> bar2 = bar; + for(int bb : bar) + for(auto& bi : bad) { + if(bi.first<bb && bb<bi.second) + {bar2.erase(bb); break;} + } + bar.swap(bar2); + } + + if(bar.empty()) + return noxchange(a, b, 0, N); + + int r = 0x3fffffff; + for(int mid: bar) { + int ll = 0, rr = N; + for(auto& bi: bad) { + if(bi.second <= mid) + ll = max(ll, bi.second); + if(mid <= bi.first) + rr = min(rr, bi.first); + } + r = min(r, totheend(0, a, b, 0, ll) + noxchange(a, b, ll, rr) + totheend(L, a, b, rr, N)); + } + return r; + } + + int noxchange(const vector<int>& a, const vector<int>& b, int S, int E) + { + int result = 0; + for(int i=S; i<E; ++i) + result += abs(a[i] - b[i]); + return result; + } + + int totheend(int END, const vector<int>& a, const vector<int>& b, int S, int E) + { + int result = 0; + for(int i=S; i<E; ++i) + result += abs(a[i] - END) + abs(END - b[i]); + return result; + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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 <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {3, 4}; + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = 4; +END +CASE(1) + int L = 10; + int a_[] = {3, 9}; + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {8, 6}; + vector <int> 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 <int> 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 <int> 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 <int> 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 <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = 45670501; +END +/* +CASE(4) + int L = ; + int a_[] = ; + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = ; + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = ; +END +CASE(5) + int L = ; + int a_[] = ; + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = ; + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); + int _ = ; +END + +*/ +} +// END CUT HERE