Mehulcoder

BNY

Oct 17th, 2020 (edited)
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. /*
  2. Author: Mehul Chaturvedi
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. using ll = long long;
  8.  
  9.  
  10. ll findMinimumAdjacentSwaps(vector<ll> &arr, ll N) {
  11.     bool visited[N + 1];
  12.  
  13.     ll minimumSwaps = 0;
  14.     memset(visited, false, sizeof(visited));
  15.  
  16.     for (int i = 0; i < N; i++) {
  17.         if (visited[i]) continue;
  18.         visited[i] = 1;
  19.         ll count = 0;
  20.         bool flag = 0;
  21.         for (int j = i + 1; j < N; ++j) {
  22.             if (visited[j]) continue;
  23.             if (arr[j] == arr[i]) {
  24.                 visited[j] = 1;
  25.                 minimumSwaps += count;
  26.                 flag = 1;
  27.                 break;
  28.             } else {
  29.                 count++;
  30.             }
  31.         }
  32.  
  33.         if (!flag) {
  34.             visited[N - 1] = 1;
  35.             minimumSwaps += count;
  36.         }
  37.     }
  38.  
  39.     return minimumSwaps;
  40. }
  41.  
  42.  
  43. void solve() {
  44.     ll n; cin >> n;
  45.  
  46.     vector<ll> a;
  47.     a.resize(n);
  48.  
  49.     map<ll, ll> freq;
  50.     for (ll i = 0; i < n; ++i) {
  51.         cin >> a[i];
  52.         freq[a[i]]++;
  53.     }
  54.  
  55.     ll notEvenFreq = 0;
  56.     ll k = 0;
  57.     map<ll, ll> m;
  58.     for (auto &elem : freq) {
  59.         if (elem.second % 2 != 0) notEvenFreq++;
  60.         m[elem.first] = k++;
  61.     }
  62.  
  63.     if (notEvenFreq > n % 2) {
  64.         cout << -1 << '\n';
  65.         return;
  66.     }
  67.  
  68.     for (ll i = 0; i < a.size(); ++i) {
  69.         a[i] = m[a[i]];
  70.     }
  71.  
  72.     ll ans = findMinimumAdjacentSwaps(a, n);
  73.  
  74.     cout << ans << '\n';
  75.     return;
  76. }
  77.  
  78. int main(int argc , char ** argv) {
  79.     ios_base::sync_with_stdio(false) ;
  80.     cin.tie(NULL) ;
  81.  
  82.     ll t = 1;
  83.     while (t--) {
  84.         solve();
  85.     }
  86.  
  87.     return 0 ;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment