Advertisement
mickypinata

USACO-T023: Sorting a Three-valued Sequence

Nov 29th, 2021
510
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: sort3
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 1000 + 5;
  11.  
  12. deque<int> ones;
  13. vector<int> lft, sortedLft;
  14. int arr[N], sorted[N];
  15.  
  16. int main(){
  17.     freopen("sort3.in", "r", stdin);
  18.     freopen("sort3.out", "w", stdout);
  19.  
  20.     int n;
  21.     scanf("%d", &n);
  22.     for(int i = 1; i <= n; ++i){
  23.         scanf("%d", &arr[i]);
  24.         sorted[i] = arr[i];
  25.     }
  26.     sort(sorted + 1, sorted + n + 1);
  27.     for(int i = 1; i <= n; ++i){
  28.         if(arr[i] != sorted[i]){
  29.             lft.push_back(arr[i]);
  30.             sortedLft.push_back(arr[i]);
  31.         }
  32.     }
  33.     sort(sortedLft.begin(), sortedLft.end());
  34.     int cnt = 0;
  35.     for(int i = 0; i < lft.size(); ++i){
  36.         if(lft[i] == 1){
  37.             ones.push_back(i);
  38.         }
  39.     }
  40.     int i;
  41.     for(i = 0; i < lft.size() && sortedLft[i] == 1; ++i){
  42.         if(lft[i] == 2){
  43.             swap(lft[i], lft[ones.front()]);
  44.             ones.pop_front();
  45.         } else if(lft[i] == 3){
  46.             swap(lft[i], lft[ones.back()]);
  47.             ones.pop_back();
  48.         }
  49.         ++cnt;
  50.     }
  51.     for(; i < lft.size() && sortedLft[i] == 2; ++i){
  52.         if(lft[i] == 3){
  53.             ++cnt;
  54.         }
  55.     }
  56.     cout << cnt << '\n';
  57.  
  58.     fclose(stdin);
  59.     fclose(stdout);
  60.     return 0;
  61. }
  62.  
Advertisement
RAW Paste Data Copied
Advertisement