Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
- #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
- #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
- #define all(a) (a).begin(), (a).end()
- #define sz(a) int((a).size())
- #define pb(a) push_back(a)
- #define mp(x, y) make_pair((x), (y))
- #define x first
- #define y second
- using namespace std;
- typedef long long li;
- typedef long double ld;
- typedef pair<int, int> pt;
- template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
- template<typename X> inline X sqr(const X& a) { return a * a; }
- const int INF = int(1e9);
- const li INF64 = li(1e18);
- const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
- const int N = 2020;
- int n, s;
- int a[N];
- inline bool read() {
- if (!(cin >> n >> s)) return false;
- s--;
- forn(i, n) assert(scanf("%d", &a[i]) == 1);
- return true;
- }
- inline int dist(int a, int b) {
- int d = abs(a - b);
- d = min(d, n - d);
- return d;
- }
- inline int odist(int a, int b) {
- int d = b - a;
- (d < 0) && (d += n);
- return d;
- }
- int nt[N];
- int z1[N], z2[N];
- int solve1(int);
- int solve2(int v) {
- int& ans = z2[v];
- if (ans != -1) return ans;
- if (nt[v] == INT_MAX) return ans = 0;
- ans = INF;
- forn(i, n)
- if (a[i] == nt[v]) {
- ans = min(ans, solve1(i) + dist(v, i));
- }
- return ans;
- }
- int solve1(int v) {
- int& ans = z1[v];
- if (ans != -1) return ans;
- ans = INF;
- for (int d = -1; d <= +1; d += 2) {
- int u = -1;
- fore(i, 1, n) {
- int vv = (v + i * d + n) % n;
- if (a[vv] == a[v]) {
- u = vv;
- break;
- }
- }
- if (u == -1)
- ans = min(ans, solve2(v));
- else {
- int dt = d == 1 ? odist(u, v) : odist(v, u);
- ans = min(ans, solve2(u) + dt);
- }
- }
- return ans;
- }
- void restore1(int);
- void restore2(int v) {
- int& ans = z2[v];
- assert(ans != -1);
- if (nt[v] == INT_MAX) return;
- forn(i, n)
- if (a[i] == nt[v] && ans == solve1(i) + dist(v, i)) {
- int d = i - v;
- (d < 0) && (d += n);
- if (d <= n - d) printf("+%d\n", d);
- else printf("-%d\n", n - d);
- return restore1(i);;
- }
- throw;
- }
- void restore1(int v) {
- int& ans = z1[v];
- assert(ans != -1);
- for (int d = -1; d <= +1; d += 2) {
- int u = -1;
- fore(i, 1, n) {
- int vv = (v + i * d + n) % n;
- if (a[vv] == a[v]) {
- u = vv;
- break;
- }
- }
- if (u == -1) {
- if (ans == solve2(v)) {
- return restore2(v);
- }
- } else {
- int dt = d == 1 ? odist(u, v) : odist(v, u);
- if (ans == solve2(u) + dt) {
- int cdt = 0;
- fore(i, 1, n) {
- int vv = (v + i * (-d) + n) % n;
- cdt++;
- if (a[vv] == a[v]) {
- printf("%c%d\n", d == +1 ? '-' : '+', cdt);
- cdt = 0;
- }
- }
- return restore2(u);
- }
- }
- }
- throw;
- }
- inline void solve() {
- memset(z1, -1, sizeof(z1));
- memset(z2, -1, sizeof(z2));
- forn(i, n) {
- nt[i] = INT_MAX;
- forn(j, n)
- if (a[j] > a[i])
- nt[i] = min(nt[i], a[j]);
- }
- //cerr << solve1(0) << endl;
- //exit(0);
- int minv = *min_element(a, a + n);
- int ans = INF;
- forn(i, n)
- if (a[i] == minv) {
- ans = min(ans, solve1(i) + dist(s, i));
- }
- cout << ans << endl;
- forn(i, n)
- if (a[i] == minv && ans == solve1(i) + dist(s, i)) {
- int d = i - s;
- (d < 0) && (d += n);
- if (d <= n - d) printf("+%d\n", d);
- else printf("-%d\n", n - d);
- restore1(i);
- break;
- }
- }
- int main() {
- #ifdef SU1
- assert(freopen("input.txt", "rt", stdin));
- //assert(freopen("output.txt", "wt", stdout));
- #endif
- cout << setprecision(10) << fixed;
- cerr << setprecision(5) << fixed;
- while (read()) {
- solve();
- //break;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment