_ash__

Untitled

Sep 24th, 2020
882
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Gene template< class
  5. #define Rics printer& operator,
  6. Gene c> struct rge{c b, e;};
  7. Gene c> rge<c> range(c i, c j){ return {i, j};}
  8. struct printer{
  9.     ~printer(){cerr<<endl;}
  10.     Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
  11.     Rics(string x){cerr<<x;return *this;}
  12.     Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
  13.     Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
  14.     Gene c >Rics(rge<c> x){
  15.         *this,"["; for(auto it = x.b; it != x.e; ++it)
  16.             *this,(it==x.b?"":", "),*it; return *this,"]";}
  17. };
  18. #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
  19. #define dbg(x) "[",#x,": ",(x),"] "
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21. int my_rand(int l, int r) {
  22.     return uniform_int_distribution<int>(l, r) (rng);
  23. }
  24.  
  25.  
  26. int main() {
  27. //    freopen("in.txt", "r", stdin);
  28.     ios::sync_with_stdio(0);
  29.     cin.tie(0);
  30.  
  31.     int n;
  32.     cin >> n;
  33.     vector<int> v(n);
  34.     for(int i = 0; i < n; i++) cin >> v[i];
  35.     vector<int> sorted = v;
  36.     sort(sorted.begin(), sorted.end());
  37.     priority_queue<pair<int,vector<int>>> pq;
  38.     pq.push({0, v});
  39.     map<vector<int>,int> dis;
  40.     dis[v] = 0;
  41.     while(pq.size() > 0) {
  42.         auto t = pq.top();
  43.         pq.pop();
  44.         auto u = t.second;
  45.         for(int i = 0; i < n; i++) {
  46.             for(int j = i+1; j < n; j++) {
  47.                 auto w = u;
  48.                 swap(w[i], w[j]);
  49.                 if(dis.find(w) == dis.end() or dis[w] > dis[u] + abs(w[i] - w[j])) {
  50.                     dis[w] = dis[u] + abs(w[i] - w[j]);
  51.                     pq.push({-dis[w], w});
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     cout << dis[sorted] << endl;
  57. }
  58.  
  59.  
  60.  
  61.  
RAW Paste Data