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) > 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 > 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() > 51 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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 > 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 > 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 > 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, > 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) > 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 > 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() > 162 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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 > 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, 5624 > 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, 92752 > 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