Guest User

Untitled

a guest
Dec 25th, 2015
1,091
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 2020;
  28.  
  29. int n, s;
  30. int a[N];
  31.  
  32. inline bool read() {
  33.     if (!(cin >> n >> s)) return false;
  34.     s--;
  35.     forn(i, n) assert(scanf("%d", &a[i]) == 1);
  36.     return true;
  37. }
  38.  
  39. inline int dist(int a, int b) {
  40.     int d = abs(a - b);
  41.     d = min(d, n - d);
  42.     return d;
  43. }
  44.  
  45. inline int odist(int a, int b) {
  46.     int d = b - a;
  47.     (d < 0) && (d += n);
  48.     return d;
  49. }
  50.  
  51. int nt[N];
  52. int z1[N], z2[N];
  53.  
  54. int solve1(int);
  55.  
  56. int solve2(int v) {
  57.     int& ans = z2[v];
  58.     if (ans != -1) return ans;
  59.     if (nt[v] == INT_MAX) return ans = 0;
  60.  
  61.     ans = INF;
  62.  
  63.     forn(i, n)
  64.         if (a[i] == nt[v]) {
  65.             ans = min(ans, solve1(i) + dist(v, i));
  66.         }
  67.  
  68.     return ans;
  69. }
  70.  
  71. int solve1(int v) {
  72.     int& ans = z1[v];
  73.     if (ans != -1) return ans;
  74.  
  75.     ans = INF;
  76.  
  77.     for (int d = -1; d <= +1; d += 2) {
  78.         int u = -1;
  79.         fore(i, 1, n) {
  80.             int vv = (v + i * d + n) % n;
  81.             if (a[vv] == a[v]) {
  82.                 u = vv;
  83.                 break;
  84.             }
  85.         }
  86.         if (u == -1)
  87.             ans = min(ans, solve2(v));
  88.         else {
  89.             int dt = d == 1 ? odist(u, v) : odist(v, u);
  90.             ans = min(ans, solve2(u) + dt);
  91.         }
  92.     }
  93.  
  94.     return ans;
  95. }
  96.  
  97. void restore1(int);
  98.  
  99. void restore2(int v) {
  100.     int& ans = z2[v];
  101.     assert(ans != -1);
  102.     if (nt[v] == INT_MAX) return;
  103.  
  104.     forn(i, n)
  105.         if (a[i] == nt[v] && ans == solve1(i) + dist(v, i)) {
  106.             int d = i - v;
  107.             (d < 0) && (d += n);
  108.             if (d <= n - d) printf("+%d\n", d);
  109.             else printf("-%d\n", n - d);
  110.             return restore1(i);;
  111.         }
  112.  
  113.     throw;
  114. }
  115.  
  116. void restore1(int v) {
  117.     int& ans = z1[v];
  118.     assert(ans != -1);
  119.  
  120.     for (int d = -1; d <= +1; d += 2) {
  121.         int u = -1;
  122.         fore(i, 1, n) {
  123.             int vv = (v + i * d + n) % n;
  124.             if (a[vv] == a[v]) {
  125.                 u = vv;
  126.                 break;
  127.             }
  128.         }
  129.         if (u == -1) {
  130.             if (ans == solve2(v)) {
  131.                 return restore2(v);
  132.             }
  133.         } else {
  134.             int dt = d == 1 ? odist(u, v) : odist(v, u);
  135.             if (ans == solve2(u) + dt) {
  136.                 int cdt = 0;
  137.                 fore(i, 1, n) {
  138.                     int vv = (v + i * (-d) + n) % n;
  139.                     cdt++;
  140.                     if (a[vv] == a[v]) {
  141.                         printf("%c%d\n", d == +1 ? '-' : '+', cdt);
  142.                         cdt = 0;
  143.                     }
  144.                 }
  145.                 return restore2(u);
  146.             }
  147.         }
  148.     }
  149.  
  150.     throw;
  151. }
  152. inline void solve() {
  153.     memset(z1, -1, sizeof(z1));
  154.     memset(z2, -1, sizeof(z2));
  155.  
  156.     forn(i, n) {
  157.         nt[i] = INT_MAX;
  158.         forn(j, n)
  159.             if (a[j] > a[i])
  160.                 nt[i] = min(nt[i], a[j]);
  161.     }
  162.  
  163.     //cerr << solve1(0) << endl;
  164.     //exit(0);
  165.  
  166.     int minv = *min_element(a, a + n);
  167.     int ans = INF;
  168.     forn(i, n)
  169.         if (a[i] == minv) {
  170.             ans = min(ans, solve1(i) + dist(s, i));
  171.         }
  172.  
  173.     cout << ans << endl;
  174.     forn(i, n)
  175.         if (a[i] == minv && ans == solve1(i) + dist(s, i)) {
  176.             int d = i - s;
  177.             (d < 0) && (d += n);
  178.             if (d <= n - d) printf("+%d\n", d);
  179.             else printf("-%d\n", n - d);
  180.             restore1(i);
  181.             break;
  182.         }
  183. }
  184.  
  185. int main() {
  186. #ifdef SU1
  187.     assert(freopen("input.txt", "rt", stdin));
  188.     //assert(freopen("output.txt", "wt", stdout));
  189. #endif
  190.    
  191.     cout << setprecision(10) << fixed;
  192.     cerr << setprecision(5) << fixed;
  193.  
  194.     while (read()) {
  195.         solve();
  196.         //break;
  197.     }
  198.    
  199.     return 0;
  200. }
Add Comment
Please, Sign In to add comment