9b83877d51 2014-05-20 kinaba: #include <iostream> 9b83877d51 2014-05-20 kinaba: #include <sstream> 9b83877d51 2014-05-20 kinaba: #include <iomanip> 9b83877d51 2014-05-20 kinaba: #include <vector> 9b83877d51 2014-05-20 kinaba: #include <string> 9b83877d51 2014-05-20 kinaba: #include <map> 9b83877d51 2014-05-20 kinaba: #include <set> 9b83877d51 2014-05-20 kinaba: #include <algorithm> 9b83877d51 2014-05-20 kinaba: #include <numeric> 9b83877d51 2014-05-20 kinaba: #include <iterator> 9b83877d51 2014-05-20 kinaba: #include <functional> 9b83877d51 2014-05-20 kinaba: #include <complex> 9b83877d51 2014-05-20 kinaba: #include <queue> 9b83877d51 2014-05-20 kinaba: #include <stack> 9b83877d51 2014-05-20 kinaba: #include <cmath> 9b83877d51 2014-05-20 kinaba: #include <cassert> 9b83877d51 2014-05-20 kinaba: #include <tuple> 9b83877d51 2014-05-20 kinaba: using namespace std; 9b83877d51 2014-05-20 kinaba: typedef long long LL; 9b83877d51 2014-05-20 kinaba: typedef complex<double> CMP; 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: class NarrowPassage { public: 9b83877d51 2014-05-20 kinaba: int minDist(int L, vector <int> a, vector <int> b) 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: sortab(a,b); 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int r = 0x3fffffff; 9b83877d51 2014-05-20 kinaba: r = min(r, solve_with_partial(L, a, b, 0, "LR", 0)); 9b83877d51 2014-05-20 kinaba: r = min(r, solve_with_partial(L, a, b, 0, "RL", 0)); 9b83877d51 2014-05-20 kinaba: return r; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: void sortab(vector <int>& a, vector <int>& b) 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: const int N = a.size(); 9b83877d51 2014-05-20 kinaba: vector<pair<int,int>> ab; 9b83877d51 2014-05-20 kinaba: for(int i=0; i<N; ++i) 9b83877d51 2014-05-20 kinaba: ab.emplace_back(a[i], b[i]); 9b83877d51 2014-05-20 kinaba: sort(ab.begin(), ab.end()); 9b83877d51 2014-05-20 kinaba: for(int i=0; i<N; ++i) { 9b83877d51 2014-05-20 kinaba: a[i] = ab[i].first; 9b83877d51 2014-05-20 kinaba: b[i] = ab[i].second; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int solve_with_partial(int L, vector<int> a, vector<int> b, int m, const string& pat, int pati) 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: const int N = a.size(); 9b83877d51 2014-05-20 kinaba: int r = 0; 9b83877d51 2014-05-20 kinaba: if(m) { 9b83877d51 2014-05-20 kinaba: if(pat[pati] == 'L') { 9b83877d51 2014-05-20 kinaba: vector<int> idx; 9b83877d51 2014-05-20 kinaba: for(int i=0; i<m; ++i) 9b83877d51 2014-05-20 kinaba: idx.push_back(i); 9b83877d51 2014-05-20 kinaba: sort(idx.begin(), idx.end(), [&](int i, int k){ 9b83877d51 2014-05-20 kinaba: return b[i]<b[k]; 9b83877d51 2014-05-20 kinaba: }); 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: for(int ii=0; ii<idx.size(); ++ii) { 9b83877d51 2014-05-20 kinaba: int i = idx[ii]; 9b83877d51 2014-05-20 kinaba: int np = ii+1; 9b83877d51 2014-05-20 kinaba: r += a[i] + np; 9b83877d51 2014-05-20 kinaba: a[i] = np; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: } else { 9b83877d51 2014-05-20 kinaba: vector<int> idx; 9b83877d51 2014-05-20 kinaba: for(int i=m; i<N; ++i) 9b83877d51 2014-05-20 kinaba: idx.push_back(i); 9b83877d51 2014-05-20 kinaba: sort(idx.begin(), idx.end(), [&](int i, int k){ 9b83877d51 2014-05-20 kinaba: return b[i]<b[k]; 9b83877d51 2014-05-20 kinaba: }); 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: for(int ii=0; ii<idx.size(); ++ii) { 9b83877d51 2014-05-20 kinaba: int i = idx[ii]; 9b83877d51 2014-05-20 kinaba: int np = L-(idx.size()-ii); 9b83877d51 2014-05-20 kinaba: r += abs(L-a[i]) + abs(L-np); 9b83877d51 2014-05-20 kinaba: a[i] = np; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: sortab(a, b); 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: if(pati == pat.size()) 9b83877d51 2014-05-20 kinaba: return r + solve(L, a, b); 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int best = 0x3fffffff; 9b83877d51 2014-05-20 kinaba: for(int mm=0; mm<N; ++mm) 9b83877d51 2014-05-20 kinaba: best = min(best, r + solve_with_partial(L, a, b, mm, pat, pati+1)); 9b83877d51 2014-05-20 kinaba: return best; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int solve(int L, const vector<int>& a, const vector<int>& b) 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: const int N = a.size(); 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: vector<pair<int,int>> bad; 9b83877d51 2014-05-20 kinaba: set<int> bar; 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: for(int i=0; i<N; ++i) 9b83877d51 2014-05-20 kinaba: for(int k=i+1; k<N; ++k) 9b83877d51 2014-05-20 kinaba: if(!(b[i]<b[k])) { 9b83877d51 2014-05-20 kinaba: bad.emplace_back(i, k+1); 9b83877d51 2014-05-20 kinaba: bar.insert(i); 9b83877d51 2014-05-20 kinaba: bar.insert(k+1); 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: set<int> bar2 = bar; 9b83877d51 2014-05-20 kinaba: for(int bb : bar) 9b83877d51 2014-05-20 kinaba: for(auto& bi : bad) { 9b83877d51 2014-05-20 kinaba: if(bi.first<bb && bb<bi.second) 9b83877d51 2014-05-20 kinaba: {bar2.erase(bb); break;} 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: bar.swap(bar2); 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: if(bar.empty()) 9b83877d51 2014-05-20 kinaba: return noxchange(a, b, 0, N); 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int r = 0x3fffffff; 9b83877d51 2014-05-20 kinaba: for(int mid: bar) { 9b83877d51 2014-05-20 kinaba: int ll = 0, rr = N; 9b83877d51 2014-05-20 kinaba: for(auto& bi: bad) { 9b83877d51 2014-05-20 kinaba: if(bi.second <= mid) 9b83877d51 2014-05-20 kinaba: ll = max(ll, bi.second); 9b83877d51 2014-05-20 kinaba: if(mid <= bi.first) 9b83877d51 2014-05-20 kinaba: rr = min(rr, bi.first); 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: r = min(r, totheend(0, a, b, 0, ll) + noxchange(a, b, ll, rr) + totheend(L, a, b, rr, N)); 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: return r; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int noxchange(const vector<int>& a, const vector<int>& b, int S, int E) 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: int result = 0; 9b83877d51 2014-05-20 kinaba: for(int i=S; i<E; ++i) 9b83877d51 2014-05-20 kinaba: result += abs(a[i] - b[i]); 9b83877d51 2014-05-20 kinaba: return result; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: int totheend(int END, const vector<int>& a, const vector<int>& b, int S, int E) 9b83877d51 2014-05-20 kinaba: { 9b83877d51 2014-05-20 kinaba: int result = 0; 9b83877d51 2014-05-20 kinaba: for(int i=S; i<E; ++i) 9b83877d51 2014-05-20 kinaba: result += abs(a[i] - END) + abs(END - b[i]); 9b83877d51 2014-05-20 kinaba: return result; 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: }; 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: // BEGIN CUT HERE 9b83877d51 2014-05-20 kinaba: #include <ctime> 9b83877d51 2014-05-20 kinaba: double start_time; string timer() 9b83877d51 2014-05-20 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 9b83877d51 2014-05-20 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 9b83877d51 2014-05-20 kinaba: { os << "{ "; 9b83877d51 2014-05-20 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 9b83877d51 2014-05-20 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 9b83877d51 2014-05-20 kinaba: void verify_case(const int& Expected, const int& Received) { 9b83877d51 2014-05-20 kinaba: bool ok = (Expected == Received); 9b83877d51 2014-05-20 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 9b83877d51 2014-05-20 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 9b83877d51 2014-05-20 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 9b83877d51 2014-05-20 kinaba: #define END verify_case(_, NarrowPassage().minDist(L, a, b));} 9b83877d51 2014-05-20 kinaba: int main(){ 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: CASE(0) 9b83877d51 2014-05-20 kinaba: int L = 5; 9b83877d51 2014-05-20 kinaba: int a_[] = {1, 2}; 9b83877d51 2014-05-20 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9b83877d51 2014-05-20 kinaba: int b_[] = {3, 4}; 9b83877d51 2014-05-20 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 9b83877d51 2014-05-20 kinaba: int _ = 4; 9b83877d51 2014-05-20 kinaba: END 9b83877d51 2014-05-20 kinaba: CASE(1) 9b83877d51 2014-05-20 kinaba: int L = 10; 9b83877d51 2014-05-20 kinaba: int a_[] = {3, 9}; 9b83877d51 2014-05-20 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9b83877d51 2014-05-20 kinaba: int b_[] = {8, 6}; 9b83877d51 2014-05-20 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 9b83877d51 2014-05-20 kinaba: int _ = 14; 9b83877d51 2014-05-20 kinaba: END 9b83877d51 2014-05-20 kinaba: CASE(2) 9b83877d51 2014-05-20 kinaba: int L = 265467; 9b83877d51 2014-05-20 kinaba: int a_[] = {133548, 103861, 29821, 199848, 92684, 219824, 215859, 62821, 172409, 109235, 9b83877d51 2014-05-20 kinaba: 38563, 148854, 24742, 174068, 205005, 75922, 87316, 5542, 57484, 40792, 9b83877d51 2014-05-20 kinaba: 25229, 152216, 21547, 22203, 84712, 231522, 235703, 184895, 100787, 174440, 9b83877d51 2014-05-20 kinaba: 156904, 84898, 185568, 108732, 260098, 89488, 221604, 104555, 165775, 90444, 9b83877d51 2014-05-20 kinaba: 81952, 149671, 209674, 22185, 45420, 41928, 16098, 65324, 90870, 35243}; 9b83877d51 2014-05-20 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9b83877d51 2014-05-20 kinaba: int b_[] = {150289, 135139, 69841, 227226, 177427, 230314, 199175, 81572, 220468, 151049, 9b83877d51 2014-05-20 kinaba: 40009, 145963, 115246, 252932, 263651, 38434, 120096, 69576, 29789, 115046, 9b83877d51 2014-05-20 kinaba: 33310, 260771, 5723, 80733, 107864, 142447, 235490, 242149, 124564, 134602, 9b83877d51 2014-05-20 kinaba: 245962, 7078, 215816, 219864, 190499, 210237, 212894, 142760, 126472, 201935, 9b83877d51 2014-05-20 kinaba: 119308, 120211, 235235, 19446, 87314, 17286, 61990, 102050, 261812, 257}; 9b83877d51 2014-05-20 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 9b83877d51 2014-05-20 kinaba: int _ = 7148670; 9b83877d51 2014-05-20 kinaba: END 9b83877d51 2014-05-20 kinaba: CASE(3) 9b83877d51 2014-05-20 kinaba: int L = 1000000; 9b83877d51 2014-05-20 kinaba: int a_[] = {706292, 756214, 490048, 228791, 567805, 353900, 640393, 562496, 217533, 934149, 9b83877d51 2014-05-20 kinaba: 938644, 127480, 777134, 999144, 41485, 544051, 417987, 767415, 971662, 959022, 9b83877d51 2014-05-20 kinaba: 670563, 34065, 518183, 750574, 546576, 207758, 159932, 429345, 670513, 271901, 9b83877d51 2014-05-20 kinaba: 476062, 392721, 774733, 502586, 915436, 120280, 951729, 699859, 581770, 268966, 9b83877d51 2014-05-20 kinaba: 79392, 888601, 378829, 350198, 939459, 644983, 605862, 721305, 269232, 137587}; 9b83877d51 2014-05-20 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9b83877d51 2014-05-20 kinaba: int b_[] = {322468, 673534, 83223, 551733, 341310, 485064, 885415, 927526, 159402, 28144, 9b83877d51 2014-05-20 kinaba: 441619, 305530, 883149, 413745, 932694, 214862, 677401, 104356, 836580, 300580, 9b83877d51 2014-05-20 kinaba: 409942, 748444, 744205, 119051, 999286, 462508, 984346, 887773, 856655, 245559, 9b83877d51 2014-05-20 kinaba: 418763, 840266, 999775, 962927, 779570, 488394, 760591, 326325, 206948, 13999, 9b83877d51 2014-05-20 kinaba: 285467, 401562, 786209, 169847, 171326, 2901, 296531, 572035, 364920, 939046}; 9b83877d51 2014-05-20 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 9b83877d51 2014-05-20 kinaba: int _ = 45670501; 9b83877d51 2014-05-20 kinaba: END 9b83877d51 2014-05-20 kinaba: /* 9b83877d51 2014-05-20 kinaba: CASE(4) 9b83877d51 2014-05-20 kinaba: int L = ; 9b83877d51 2014-05-20 kinaba: int a_[] = ; 9b83877d51 2014-05-20 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9b83877d51 2014-05-20 kinaba: int b_[] = ; 9b83877d51 2014-05-20 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 9b83877d51 2014-05-20 kinaba: int _ = ; 9b83877d51 2014-05-20 kinaba: END 9b83877d51 2014-05-20 kinaba: CASE(5) 9b83877d51 2014-05-20 kinaba: int L = ; 9b83877d51 2014-05-20 kinaba: int a_[] = ; 9b83877d51 2014-05-20 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 9b83877d51 2014-05-20 kinaba: int b_[] = ; 9b83877d51 2014-05-20 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 9b83877d51 2014-05-20 kinaba: int _ = ; 9b83877d51 2014-05-20 kinaba: END 9b83877d51 2014-05-20 kinaba: 9b83877d51 2014-05-20 kinaba: */ 9b83877d51 2014-05-20 kinaba: } 9b83877d51 2014-05-20 kinaba: // END CUT HERE