Advertisement
MathQ_

Untitled

Dec 13th, 2020
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  2. #pragma GCC optimize 03
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <iterator>
  8. #include <cmath>
  9. #include <ctime>
  10. #include <vector>
  11. #include <deque>
  12. #include <queue>
  13. #include <set>
  14. #include <map>
  15. #include <stack>
  16. #include <string>
  17. #include <random>
  18. #include <numeric>
  19. #include <unordered_set>
  20.  
  21. typedef long long ll;
  22. typedef long double lb;
  23.  
  24. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  25. #define file_in freopen("input.txt", "r", stdin);
  26. #define file_in_out freopen("knapsack.in", "r", stdin); freopen("knapsack.out", "w", stdout);
  27. #define mp make_pair
  28. #define pii pair<int, int>
  29. #define all(x) (x).begin(), (x).end()
  30. #define fi first
  31. #define se second
  32.  
  33. using namespace std;
  34.  
  35. template<typename T>
  36. istream& operator>>(istream &in, vector<T> &v) {
  37.     for (auto &it : v) {
  38.         in >> it;
  39.     }
  40.     return in;
  41. }
  42.  
  43. template<typename T>
  44. ostream& operator<<(ostream &out, vector<T> &v) {
  45.     if (!v.empty()) {
  46.         out << v.front();
  47.         for (int i = 1; i < v.size(); ++i) {
  48.             out << " " << v[i];
  49.         }
  50.     }
  51.     return out;
  52. }
  53.  
  54. int main() {
  55.     fast
  56. //  file_in
  57. //  file_in_out
  58.      
  59.     int n, j;
  60.     cin >> n;
  61.     vector<int> a(n);
  62.     cin >> a;
  63.     vector<int> b = a;
  64.     map<pii, vector<int>> cnt;
  65.     map<int, int> cntt;
  66.     sort(all(b));
  67.     vector<pii> ans;
  68.     for (int i = 0; i < n; ++i) cnt[mp(a[i], b[i])].push_back(i);
  69.     for (int i = 0; i < n; ++i) {
  70.         if (!cntt[i] && a[i] != b[i] && cnt[mp(b[i], a[i])].size()) {
  71.             j = cnt[mp(b[i], a[i])][cnt[mp(b[i], a[i])].size() - 1];
  72.             swap(a[i], a[j]);
  73.             ans.emplace_back(i + 1, j + 1);
  74.             cnt[mp(b[i], a[i])].pop_back();
  75.             ++cntt[i]; ++cntt[j];
  76.         }
  77.     }
  78.     for (int i = 1; i < n; ++i) if (a[i] < a[i - 1]) {cout << "No"; return 0;}
  79.     cout << "Yes" << "\n" << ans.size() << "\n";
  80.     for(auto el : ans) cout << el.fi << " " << el.se << endl;
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement