fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8.  
  9. template <typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  10.  
  11. #ifdef LOCAL 
  12. #include "C:\CP\debug.h"
  13. #else
  14. #define debug(...)
  15. #endif
  16.  
  17. using ll = long long;
  18. const char nl = '\n';
  19. #define fi first
  20. #define se second
  21. #define pb push_back
  22. typedef vector<int> vi;
  23. #define sz(v) (int)(v.size())
  24. #define all(x) x.begin(),x.end()
  25. #define rall(x) x.rbegin(),x.rend()
  26. #define unq(x) sort(all(x)) , x.erase(unique(all(x)),x.end())
  27.  
  28. #include <vector>
  29. #include <algorithm>
  30.  
  31. int minSwapsToSort(std::vector<int>& nums) {
  32.     int n = nums.size();
  33.     std::vector<std::pair<int, int>> arrPos(n);
  34.     for (int i = 0; i < n; i++) {
  35.         arrPos[i] = {nums[i], i};
  36.     }
  37.     std::sort(arrPos.begin(), arrPos.end());
  38.     std::vector<bool> visited(n, false);
  39.     int swaps = 0;
  40.     for (int i = 0; i < n; i++) {
  41.         if (visited[i] || arrPos[i].second == i)
  42.             continue;
  43.         int cycleSize = 0;
  44.         int j = i;
  45.         while (!visited[j]) {
  46.             visited[j] = true;
  47.             j = arrPos[j].second;
  48.             cycleSize++;
  49.         }
  50.         if (cycleSize > 0)
  51.             swaps += (cycleSize - 1);
  52.     }
  53.     return swaps;
  54. }
  55.  
  56.  
  57. void leftCyclicShift(std::vector<int>& nums) {
  58.     if (nums.empty()) return;
  59.     int first = nums[0];
  60.     for (int i = 0; i < nums.size() - 1; i++) {
  61.         nums[i] = nums[i + 1];
  62.     }
  63.     nums[nums.size() - 1] = first;
  64. }
  65.  
  66.  
  67. void Solve() {
  68.    int n; cin >> n;
  69.    vector<int> arr(n); for(auto& x: arr)cin >> x;
  70.    vector<int> brr(arr);
  71.    sort(all(brr));
  72.    if(arr == brr){
  73.       cout << 0 << nl;
  74.       return;
  75.    }
  76.    int ans = INT_MAX;
  77.    for(int shifts = 1; shifts < n; ++shifts) {
  78.       leftCyclicShift(arr);
  79.       if(arr == brr){
  80.          ans = min(ans,shifts);
  81.          break;
  82.       }
  83.       int mn = minSwapsToSort(arr);
  84.       ans = min(ans,shifts + mn);
  85.    }
  86.    cout << ans << nl;
  87. }
  88.  
  89. signed main() {
  90.     ios::sync_with_stdio(false); cin.tie(0);
  91.     #ifdef LOCAL
  92.     freopen("input.txt", "rt", stdin);
  93.     freopen("output.txt", "w", stdout);
  94.     #endif
  95.  
  96.  
  97.     int tt = 1;
  98.     //cin >> tt;
  99.     while ( tt--) {
  100.       Solve();
  101.     } 
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/O8wOi9
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!