Advertisement
Um_nik

Untitled

Nov 1st, 2020
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <queue>
  12. #include <ctime>
  13. #include <cassert>
  14. #include <complex>
  15. #include <string>
  16. #include <cstring>
  17. #include <chrono>
  18. #include <random>
  19. #include <bitset>
  20. using namespace std;
  21.  
  22. #ifdef LOCAL
  23.     #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
  24. #else
  25.     #define eprintf(...) 42
  26. #endif
  27.  
  28. using ll = long long;
  29. using ld = long double;
  30. using uint = unsigned int;
  31. using ull = unsigned long long;
  32. template<typename T>
  33. using pair2 = pair<T, T>;
  34. using pii = pair<int, int>;
  35. using pli = pair<ll, int>;
  36. using pll = pair<ll, ll>;
  37. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  38. ll myRand(ll B) {
  39.     return (ull)rng() % B;
  40. }
  41.  
  42. #define pb push_back
  43. #define mp make_pair
  44. #define all(x) (x).begin(),(x).end()
  45. #define fi first
  46. #define se second
  47.  
  48. clock_t startTime;
  49. double getCurrentTime() {
  50.     return (double)(clock() - startTime) / CLOCKS_PER_SEC;
  51. }
  52.  
  53. struct Move {
  54.     int id;
  55.     int x, y, z;
  56.  
  57.     Move() : id(-1), x(), y(), z() {}
  58.     Move(int _id, int _x, int _y, int _z) : id(_id), x(_x), y(_y), z(_z) {}
  59. };
  60.  
  61. const int N = 9;
  62. const int M = 40404;
  63. const int TT = 100100;
  64. int dist[M][N];
  65. Move par[M][N];
  66. int tr[M][N][N][N];
  67. int CU, CD, CX;
  68. int n;
  69. int f[N];
  70. vector<int> fromId[M];
  71. vector<pii> Q[TT];
  72. vector<int> ANS;
  73.  
  74. const int UP = 1;
  75. const int DOWN = 2;
  76. const int SHIFT_PRESS = 3;
  77. const int SHIFT_RELEASE = 4;
  78. const int CTRL_X = 5;
  79. const int CTRL_V = 6;
  80. string COMM[] = {"Up", "Down", "Shift-Press", "Shift-Release", "Ctrl+X", "Ctrl+V"};
  81.  
  82. void addMove(Move MV) {
  83.     vector<int> cur;
  84.     if (MV.z == -1) {
  85.         if (MV.y == -1)
  86.             cur.push_back(UP);
  87.         else
  88.             cur.push_back(DOWN);
  89.     } else {
  90.         int st = MV.x;
  91.         if (MV.y < 0) st += MV.y;
  92.         cur.push_back(SHIFT_PRESS);
  93.         for (int i = 0; i < MV.y; i++)
  94.             cur.push_back(DOWN);
  95.         for (int i = 0; i > MV.y; i--)
  96.             cur.push_back(UP);
  97.         cur.push_back(SHIFT_RELEASE);
  98.         cur.push_back(CTRL_X);
  99.         for (int i = st; i < MV.z; i++)
  100.             cur.push_back(DOWN);
  101.         for (int i = st; i > MV.z; i--)
  102.             cur.push_back(UP);
  103.         cur.push_back(CTRL_V);
  104.     }
  105.     reverse(all(cur));
  106.     for (int x : cur) ANS.push_back(x);
  107. }
  108.  
  109. void printCommand(int x) {
  110.     cout << COMM[x - 1] << endl;
  111. }
  112.  
  113. int toId(const vector<int> &p) {
  114.     int res = 0;
  115.     for (int i = 0; i < n; i++) {
  116.         for (int j = i + 1; j < n; j++)
  117.             if (p[j] < p[i])
  118.                 res += f[n - 1 - i];
  119.     }
  120.     return res;
  121. }
  122.  
  123. void relaxDist(int id, int pos, int newDist, Move P) {
  124.     if (dist[id][pos] <= newDist) return;
  125.     dist[id][pos] = newDist;
  126.     par[id][pos] = P;
  127.     Q[newDist].push_back(mp(id, pos));
  128. }
  129.  
  130. int main()
  131. {
  132.     startTime = clock();
  133. //  freopen("input.txt", "r", stdin);
  134. //  freopen("output.txt", "w", stdout);
  135.  
  136.     f[0] = 1;
  137.     for (int i = 1; i < N; i++)
  138.         f[i] = f[i - 1] * i;
  139.  
  140.     scanf("%d", &n);
  141.  
  142.     scanf("%d%d", &CU, &CD);
  143.     for (int i = 0; i < 4; i++) {
  144.         int x;
  145.         scanf("%d", &x);
  146.         CX += x;
  147.     }
  148.  
  149.     fromId[0] = vector<int>(n);
  150.     for (int i = 0; i < n; i++)
  151.         fromId[0][i] = i;
  152.     for (int t = 1; t < f[n]; t++) {
  153.         fromId[t] = fromId[t - 1];
  154.         next_permutation(all(fromId[t]));
  155.     }
  156.     for (int id = 0; id < f[n]; id++) {
  157.         vector<int> p = fromId[id];
  158.         for (int i = 0; i < n; i++)
  159.             for (int len = 1; i + len <= n; len++) {
  160.                 vector<int> q;
  161.                 q.reserve(n - len);
  162.                 for (int j = 0; j < n; j++) {
  163.                     if (i <= j && j < i + len) continue;
  164.                     q.push_back(p[j]);
  165.                 }
  166.                 for (int t = 0; t + len <= n; t++) {
  167.                     vector<int> w;
  168.                     w.reserve(n);
  169.                     for (int j = 0; j < t; j++)
  170.                         w.push_back(q[j]);
  171.                     for (int j = i; j < i + len; j++)
  172.                         w.push_back(p[j]);
  173.                     for (int j = t; j < n - len; j++)
  174.                         w.push_back(q[j]);
  175.                     tr[id][i][len][t] = toId(w);
  176.                 }
  177.             }
  178.     }
  179.     eprintf("precalc = %.5lf\n", getCurrentTime());
  180.  
  181.     int S, T;
  182.     vector<int> p(n);
  183.     for (int i = 0; i < n; i++) {
  184.         scanf("%d", &p[i]);
  185.         p[i]--;
  186.     }
  187.     S = toId(p);
  188.     for (int i = 0; i < n; i++) {
  189.         scanf("%d", &p[i]);
  190.         p[i]--;
  191.     }
  192.     T = toId(p);
  193.  
  194.     for (int id = 0; id < f[n]; id++)
  195.         for (int i = 0; i <= n; i++)
  196.             dist[id][i] = TT;
  197.     relaxDist(S, 0, 0, Move());
  198.  
  199.     for (int D = 0; D < TT; D++) {
  200.         //eprintf("D = %d\n", D);
  201.         while(!Q[D].empty()) {
  202.             pii V = Q[D].back();
  203.             Q[D].pop_back();
  204.             int id = V.first, pos = V.second;
  205.             if (dist[id][pos] != D) continue;
  206.             if (pos > 0) {
  207.                 relaxDist(id, pos - 1, D + CU, Move(id, pos, -1, -1));
  208.             }
  209.             if (pos + 1 <= n) {
  210.                 relaxDist(id, pos + 1, D + CD, Move(id, pos, 1, -1));
  211.             }
  212.             for (int len = 1; pos + len <= n; len++)
  213.                 for (int npos = 0; npos + len <= n; npos++) {
  214.                     int nid = tr[id][pos][len][npos];
  215.                     if (id == nid) continue;
  216.                     relaxDist(nid, npos + len,
  217.                         D + CX + CD * len + max(0, npos - pos) * CD + max(0, pos - npos) * CU,
  218.                         Move(id, pos, len, npos));
  219.                 }
  220.             for (int len = 1; len <= pos; len++)
  221.                 for (int npos = 0; npos + len <= n; npos++) {
  222.                     int nid = tr[id][pos - len][len][npos];
  223.                     if (id == nid) continue;
  224.                     relaxDist(nid, npos + len,
  225.                         D + CX + CU * len + max(0, npos - (pos - len)) * CD + max(0, (pos - len) - npos) * CU,
  226.                         Move(id, pos, -len, npos));
  227.                 }
  228.         }
  229.     }
  230.     int pos = 0;
  231.     for (int i = 0; i <= n; i++)
  232.         if (dist[T][pos] > dist[T][i])
  233.             pos = i;
  234.     printf("%d ", dist[T][pos]);
  235.  
  236.     //return 0;
  237.  
  238.     while(dist[T][pos] > 0) {
  239.         Move MV = par[T][pos];
  240.         addMove(MV);
  241.         T = MV.id;
  242.         pos = MV.x;
  243.     }
  244.     reverse(all(ANS));
  245.     printf("%d\n", (int)ANS.size());
  246.     for (int x : ANS) {
  247.         printCommand(x);
  248.     }
  249.  
  250.     return 0;
  251. }
  252.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement