fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<int,int>> ans;
  5.  
  6. void solve(vector<int>& P, int offset) {
  7.     int n = P.size();
  8.     if (n <= 1) return;
  9.  
  10.     int pos = find(P.begin(), P.end(), n) - P.begin(); // n의 위치
  11.     if (pos != n-1) {
  12.         for (int i = pos; i < n-1; i++) {
  13.             swap(P[i], P[i+1]);
  14.             ans.push_back({i+1+offset, i+2+offset});
  15.         }
  16.     }
  17.  
  18.     // 마지막 원소를 제외한 나머지 부분 재귀 처리
  19.     vector<int> sub(P.begin(), P.end()-1);
  20.     solve(sub, offset);
  21. }
  22.  
  23. int main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(nullptr);
  26.  
  27.     int n;
  28.     cin >> n;
  29.     vector<int> P(n);
  30.     for (int i = 0; i < n; i++) cin >> P[i];
  31.  
  32.     // 역전 개수 parity 체크
  33.     long long inv = 0;
  34.     for (int i = 0; i < n; i++)
  35.         for (int j = i+1; j < n; j++)
  36.             if (P[i] > P[j]) inv++;
  37.  
  38.     long long total = 1LL * n * (n-1) / 2;
  39.     if ((inv % 2) != (total % 2)) {
  40.         cout << 0 << "\n";
  41.         return 0;
  42.     }
  43.  
  44.     vector<int> Pcopy = P;
  45.     solve(Pcopy, 0);
  46.  
  47.     cout << 1 << "\n";
  48.     for (auto &p : ans)
  49.         cout << p.first << " " << p.second << "\n";
  50.  
  51.     return 0;
  52. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
3
1 3 2
stdout
copy 
1
2 3
https://ideone.com/wv27LD
language:
C++ (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!