Advertisement
Guest User

Untitled

a guest
Jun 27th, 2017
447
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = (1e6)+1;
  4.  
  5. int n, load, p[MAX];
  6. multiset<int> turn;
  7. long long res[MAX];
  8. int main() {
  9. ios::sync_with_stdio(false);
  10. cin.tie(0);
  11. cin >> n;
  12. for(int i = 1; i <= n; i++) {
  13. cin >> p[i];
  14. if(p[i] < i) load--, turn.insert(i-p[i]);
  15. else load++;
  16. res[0] += abs(p[i] - i);
  17. }
  18. long long curr = res[0];
  19. for(int i = 1; i <= n; i++) {
  20. curr += load - p[i] + abs(p[i] - n);
  21. load -= 2;
  22. turn.insert(i+n-p[i]);
  23. res[i] = curr;
  24. while(!turn.empty() && *turn.begin() == i) {
  25. load += 2;
  26. turn.erase(turn.begin());
  27. }
  28. }
  29. int mn = 0;
  30. for(int i = 1; i <= n; i++) if(res[i] < res[mn]) mn = i;
  31. cout << res[mn] << ' ' << (n-mn)%n;
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement