Overview
| SHA1 Hash: | 9b83877d51020aeb5deaa7f5883a0c23f343c1cb |
|---|---|
| Date: | 2014-05-20 12:06:03 |
| User: | kinaba |
| Comment: | tco14 |
| 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/TCO14-2A-U/1A.cpp version [e46d73f6a1ae557a]
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 SixteenBricks { public: 23 + int maximumSurface(vector <int> height) 24 + { 25 + sort(height.begin(), height.end()); 26 + int total = accumulate(height.begin(), height.end(), 0) * 4 + 16; 27 + 28 + total -= height[0] * 4 * 2; 29 + total -= height[1] * 4 * 2; 30 + total -= height[2] * 3 * 2; 31 + total -= height[3] * 3 * 2; 32 + total -= height[4] * 3 * 2; 33 + total -= height[5] * 3 * 2; 34 + total -= height[6] * 2 * 2; 35 + total -= height[7] * 2 * 2; 36 + return total; 37 + } 38 +}; 39 + 40 +// BEGIN CUT HERE 41 +#include <ctime> 42 +double start_time; string timer() 43 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 44 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 45 + { os << "{ "; 46 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 47 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 48 +void verify_case(const int& Expected, const int& Received) { 49 + bool ok = (Expected == Received); 50 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 51 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 52 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 53 +#define END verify_case(_, SixteenBricks().maximumSurface(height));} 54 +int main(){ 55 + 56 +CASE(0) 57 + int height_[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; 58 + vector <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); 59 + int _ = 32; 60 +END 61 +CASE(1) 62 + int height_[] = {1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2}; 63 + vector <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); 64 + int _ = 64; 65 +END 66 +CASE(2) 67 + int height_[] = {77, 78, 58, 34, 30, 20, 8, 71, 37, 74, 21, 45, 39, 16, 4, 59} 68 +; 69 + vector <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); 70 + int _ = 1798; 71 +END 72 +/* 73 +CASE(3) 74 + int height_[] = ; 75 + vector <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); 76 + int _ = ; 77 +END 78 +CASE(4) 79 + int height_[] = ; 80 + vector <int> height(height_, height_+sizeof(height_)/sizeof(*height_)); 81 + int _ = ; 82 +END 83 +*/ 84 +} 85 +// END CUT HERE
Added SRM/TCO14-2A-U/2B-U.cpp version [96e71ffa177d8277]
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 NarrowPassage { public: 23 + int minDist(int L, vector <int> a, vector <int> b) 24 + { 25 + sortab(a,b); 26 + 27 + int r = 0x3fffffff; 28 + r = min(r, solve_with_partial(L, a, b, 0, "LR", 0)); 29 + r = min(r, solve_with_partial(L, a, b, 0, "RL", 0)); 30 + return r; 31 + } 32 + 33 + void sortab(vector <int>& a, vector <int>& b) 34 + { 35 + const int N = a.size(); 36 + vector<pair<int,int>> ab; 37 + for(int i=0; i<N; ++i) 38 + ab.emplace_back(a[i], b[i]); 39 + sort(ab.begin(), ab.end()); 40 + for(int i=0; i<N; ++i) { 41 + a[i] = ab[i].first; 42 + b[i] = ab[i].second; 43 + } 44 + } 45 + 46 + int solve_with_partial(int L, vector<int> a, vector<int> b, int m, const string& pat, int pati) 47 + { 48 + const int N = a.size(); 49 + int r = 0; 50 + if(m) { 51 + if(pat[pati] == 'L') { 52 + vector<int> idx; 53 + for(int i=0; i<m; ++i) 54 + idx.push_back(i); 55 + sort(idx.begin(), idx.end(), [&](int i, int k){ 56 + return b[i]<b[k]; 57 + }); 58 + 59 + for(int ii=0; ii<idx.size(); ++ii) { 60 + int i = idx[ii]; 61 + int np = ii+1; 62 + r += a[i] + np; 63 + a[i] = np; 64 + } 65 + } else { 66 + vector<int> idx; 67 + for(int i=m; i<N; ++i) 68 + idx.push_back(i); 69 + sort(idx.begin(), idx.end(), [&](int i, int k){ 70 + return b[i]<b[k]; 71 + }); 72 + 73 + for(int ii=0; ii<idx.size(); ++ii) { 74 + int i = idx[ii]; 75 + int np = L-(idx.size()-ii); 76 + r += abs(L-a[i]) + abs(L-np); 77 + a[i] = np; 78 + } 79 + } 80 + sortab(a, b); 81 + } 82 + 83 + if(pati == pat.size()) 84 + return r + solve(L, a, b); 85 + 86 + int best = 0x3fffffff; 87 + for(int mm=0; mm<N; ++mm) 88 + best = min(best, r + solve_with_partial(L, a, b, mm, pat, pati+1)); 89 + return best; 90 + } 91 + 92 + int solve(int L, const vector<int>& a, const vector<int>& b) 93 + { 94 + const int N = a.size(); 95 + 96 + vector<pair<int,int>> bad; 97 + set<int> bar; 98 + 99 + for(int i=0; i<N; ++i) 100 + for(int k=i+1; k<N; ++k) 101 + if(!(b[i]<b[k])) { 102 + bad.emplace_back(i, k+1); 103 + bar.insert(i); 104 + bar.insert(k+1); 105 + } 106 + 107 + { 108 + set<int> bar2 = bar; 109 + for(int bb : bar) 110 + for(auto& bi : bad) { 111 + if(bi.first<bb && bb<bi.second) 112 + {bar2.erase(bb); break;} 113 + } 114 + bar.swap(bar2); 115 + } 116 + 117 + if(bar.empty()) 118 + return noxchange(a, b, 0, N); 119 + 120 + int r = 0x3fffffff; 121 + for(int mid: bar) { 122 + int ll = 0, rr = N; 123 + for(auto& bi: bad) { 124 + if(bi.second <= mid) 125 + ll = max(ll, bi.second); 126 + if(mid <= bi.first) 127 + rr = min(rr, bi.first); 128 + } 129 + r = min(r, totheend(0, a, b, 0, ll) + noxchange(a, b, ll, rr) + totheend(L, a, b, rr, N)); 130 + } 131 + return r; 132 + } 133 + 134 + int noxchange(const vector<int>& a, const vector<int>& b, int S, int E) 135 + { 136 + int result = 0; 137 + for(int i=S; i<E; ++i) 138 + result += abs(a[i] - b[i]); 139 + return result; 140 + } 141 + 142 + int totheend(int END, const vector<int>& a, const vector<int>& b, int S, int E) 143 + { 144 + int result = 0; 145 + for(int i=S; i<E; ++i) 146 + result += abs(a[i] - END) + abs(END - b[i]); 147 + return result; 148 + } 149 +}; 150 + 151 +// BEGIN CUT HERE 152 +#include <ctime> 153 +double start_time; string timer() 154 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 155 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 156 + { os << "{ "; 157 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 158 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 159 +void verify_case(const int& Expected, const int& Received) { 160 + bool ok = (Expected == Received); 161 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 162 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 163 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 164 +#define END verify_case(_, NarrowPassage().minDist(L, a, b));} 165 +int main(){ 166 + 167 +CASE(0) 168 + int L = 5; 169 + int a_[] = {1, 2}; 170 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 171 + int b_[] = {3, 4}; 172 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 173 + int _ = 4; 174 +END 175 +CASE(1) 176 + int L = 10; 177 + int a_[] = {3, 9}; 178 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 179 + int b_[] = {8, 6}; 180 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 181 + int _ = 14; 182 +END 183 +CASE(2) 184 + int L = 265467; 185 + int a_[] = {133548, 103861, 29821, 199848, 92684, 219824, 215859, 62821, 172409, 109235, 186 +38563, 148854, 24742, 174068, 205005, 75922, 87316, 5542, 57484, 40792, 187 +25229, 152216, 21547, 22203, 84712, 231522, 235703, 184895, 100787, 174440, 188 +156904, 84898, 185568, 108732, 260098, 89488, 221604, 104555, 165775, 90444, 189 +81952, 149671, 209674, 22185, 45420, 41928, 16098, 65324, 90870, 35243}; 190 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 191 + int b_[] = {150289, 135139, 69841, 227226, 177427, 230314, 199175, 81572, 220468, 151049, 192 +40009, 145963, 115246, 252932, 263651, 38434, 120096, 69576, 29789, 115046, 193 +33310, 260771, 5723, 80733, 107864, 142447, 235490, 242149, 124564, 134602, 194 +245962, 7078, 215816, 219864, 190499, 210237, 212894, 142760, 126472, 201935, 195 +119308, 120211, 235235, 19446, 87314, 17286, 61990, 102050, 261812, 257}; 196 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 197 + int _ = 7148670; 198 +END 199 +CASE(3) 200 + int L = 1000000; 201 + int a_[] = {706292, 756214, 490048, 228791, 567805, 353900, 640393, 562496, 217533, 934149, 202 +938644, 127480, 777134, 999144, 41485, 544051, 417987, 767415, 971662, 959022, 203 +670563, 34065, 518183, 750574, 546576, 207758, 159932, 429345, 670513, 271901, 204 +476062, 392721, 774733, 502586, 915436, 120280, 951729, 699859, 581770, 268966, 205 +79392, 888601, 378829, 350198, 939459, 644983, 605862, 721305, 269232, 137587}; 206 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 207 + int b_[] = {322468, 673534, 83223, 551733, 341310, 485064, 885415, 927526, 159402, 28144, 208 +441619, 305530, 883149, 413745, 932694, 214862, 677401, 104356, 836580, 300580, 209 +409942, 748444, 744205, 119051, 999286, 462508, 984346, 887773, 856655, 245559, 210 +418763, 840266, 999775, 962927, 779570, 488394, 760591, 326325, 206948, 13999, 211 +285467, 401562, 786209, 169847, 171326, 2901, 296531, 572035, 364920, 939046}; 212 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 213 + int _ = 45670501; 214 +END 215 +/* 216 +CASE(4) 217 + int L = ; 218 + int a_[] = ; 219 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 220 + int b_[] = ; 221 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 222 + int _ = ; 223 +END 224 +CASE(5) 225 + int L = ; 226 + int a_[] = ; 227 + vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 228 + int b_[] = ; 229 + vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 230 + int _ = ; 231 +END 232 + 233 +*/ 234 +} 235 +// END CUT HERE