/**
* Cute problem~ I started by experimenting different examples. Nope. I noticed nothing,
* and was stuck for a while. I initially guessed that maybe Aryan never moves a book to
* an intermediate table, rather than directly to its destination, but I quickly dismissed
* the thought because of (2,3,0,1). In fact, the min num of steps to solve (2,3,0,1) is 8,
* not 10. Then, I wonder, can I prove that 8 is the minimum? Yep! That was how I found the
* way. I chose to consider some monovariant/invariant. A common one for sorting is
* sum{|i - p_i|}, i.e. the sum of distances between a book and its destination. This sum
* is exactly 8 for (2,3,0,1), so 8 is indeed the min.
*
* sum{|i-p_i|} is a minimum because every step of Aryan can only bring a book at most 1
* table closer to its destination. The min is achieved iff Aryan takes a book towards its
* right place at every step, regardless of whether a book has been put down in an
* intermediate table. What's a convenient way to achieve sum{|i-p_i|}? Note that a
* permutation can be seen as the collection of some cycles. For each cycle, we can just
* pick the books in it, in order. Let's call such traversal the "min-cost traversal" of
* the cycle. For example, if the perm is just one cycle of size n, then the sum is indeed
* sum{|i-p_i|}, achieved with just one complete "min-cost traversal".
*
* For convenience, let's call sum{|i-p_i|} the "principal cost". Note that the principal
* cost isn't always the min num of steps. Let c_1, c_2, ..., c_k be all the non-trivial
* cycles (len>1, containing elements that have to be moved) representing our perm. Let the
* "repr range" of c_i be [smallest_j_in_c_i, greatest_j_in_c_i]. We've already
* established that a single cycle can be handled with one min-cost traversal. If the repr
* ranges of c_i and c_j intersect, it can be proved that their min-cost traversal can be
* "combined" (with no additional steps needed), which means the k cycles' repr ranges can
* now be seen as a few disjoint repr ranges. The gaps between these disjoint ranges are
* definitely not covered in the principal cost, but Aryan must walk through each gap at
* least twice (since he has to return to s too).
*
* Finally, if p[i] != i, we're done; but if p[i] = i, the two costs above aren't enough.
* Call a position i bad iff p[i] != i. Specifically, we can prove that an additional cost
* is needed to go to the nearest bad position iff s isn't in an aforementioned "gap".
*
* Time Complexity: O(n * log(n)) (maths, permutation)
* Implementation 1 (Full solution)
*/
#include <bits/stdc++.h>
#include "books.h"
typedef long long ll;
typedef std::vector<int> vec;
ll minimum_walk(vec perm, int s) {
int n = perm.size();
std::vector<bool> visited(n, false);
vec ls, rs;
int cs = 0, nearest = n;
ll cost = 0;
for (int src = 0; src < n; src++) {
if (visited[src] || src == perm[src])
continue;
int l = n, r = -1;
for (int pt = src;; pt = perm[pt]) {
visited[pt] = true;
nearest = std::min(nearest, std::abs(s - pt));
cost += std::abs(pt - perm[pt]), l = std::min(l, pt), r = std::max(r, pt);
if (perm[pt] == src)
break;
}
ls.push_back(l);
rs.push_back(r);
cs++;
}
if (cs == 0)
return 0;
std::sort(ls.begin(), ls.end());
std::sort(rs.begin(), rs.end());
cost += 2 * nearest;
for (int t = ls.front(), i = 0, j = 0, level = 0; t < rs.back(); t++) {
while (i < cs && ls[i] <= t)
level++, i++;
while (j < cs && rs[j] <= t)
level--, j++;
if (s == t && level == 0)
cost -= 2 * nearest;
if (level == 0)
cost += 2;
}
return cost;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
296 KB |
Output is correct |
| 16 |
Correct |
0 ms |
304 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
300 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
296 KB |
Output is correct |
| 16 |
Correct |
0 ms |
304 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
300 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
296 KB |
Output is correct |
| 16 |
Correct |
0 ms |
304 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
300 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
212 KB |
Output is correct |
| 30 |
Correct |
92 ms |
14956 KB |
Output is correct |
| 31 |
Correct |
102 ms |
14936 KB |
Output is correct |
| 32 |
Correct |
76 ms |
14952 KB |
Output is correct |
| 33 |
Correct |
117 ms |
16720 KB |
Output is correct |
| 34 |
Correct |
91 ms |
16832 KB |
Output is correct |
| 35 |
Correct |
96 ms |
16840 KB |
Output is correct |
| 36 |
Correct |
96 ms |
16716 KB |
Output is correct |
| 37 |
Correct |
109 ms |
15196 KB |
Output is correct |
| 38 |
Correct |
81 ms |
14936 KB |
Output is correct |
| 39 |
Correct |
94 ms |
14940 KB |
Output is correct |
| 40 |
Correct |
81 ms |
14952 KB |
Output is correct |
| 41 |
Correct |
88 ms |
14924 KB |
Output is correct |
| 42 |
Correct |
90 ms |
14940 KB |
Output is correct |
| 43 |
Correct |
102 ms |
17100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
296 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
296 KB |
Output is correct |
| 16 |
Correct |
0 ms |
304 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
300 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
212 KB |
Output is correct |
| 30 |
Correct |
92 ms |
14956 KB |
Output is correct |
| 31 |
Correct |
102 ms |
14936 KB |
Output is correct |
| 32 |
Correct |
76 ms |
14952 KB |
Output is correct |
| 33 |
Correct |
117 ms |
16720 KB |
Output is correct |
| 34 |
Correct |
91 ms |
16832 KB |
Output is correct |
| 35 |
Correct |
96 ms |
16840 KB |
Output is correct |
| 36 |
Correct |
96 ms |
16716 KB |
Output is correct |
| 37 |
Correct |
109 ms |
15196 KB |
Output is correct |
| 38 |
Correct |
81 ms |
14936 KB |
Output is correct |
| 39 |
Correct |
94 ms |
14940 KB |
Output is correct |
| 40 |
Correct |
81 ms |
14952 KB |
Output is correct |
| 41 |
Correct |
88 ms |
14924 KB |
Output is correct |
| 42 |
Correct |
90 ms |
14940 KB |
Output is correct |
| 43 |
Correct |
102 ms |
17100 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
296 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 45 |
Halted |
0 ms |
0 KB |
- |
