fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. int main() {
  7.     int t;
  8.     cin >> t;
  9.     while (t--) {
  10.         int n, time = 0;
  11.         cin >> n;
  12.         int a[n], b[n], c[3] = {0};
  13.         vector<pair<int, int>> swaps;
  14.         for(int i = 0; i < 3; i++) {
  15.             c[i] = 0;
  16.         }
  17.         for (int i = 0; i < n; i++) {
  18.             cin >> a[i];
  19.             if (a[i] < 3) {
  20.                 c[a[i]]++;
  21.             }
  22.         }
  23.         for(int i = 0; i < c[0]; i++) {
  24.             b[i] = 0;
  25.         }
  26.         for(int i = c[0]; i < c[0] + c[1]; i++) {
  27.             b[i] = 1;
  28.         }
  29.         for(int i = c[0] + c[1]; i < n; i++) {
  30.             b[i] = 2;
  31.         }
  32.         for(int i = n - 1; i >= 0; i--) {
  33.             if(a[i] != b[i]) {
  34.                 if(abs(a[i] - b[i]) == 1) {
  35.                     for(int j = n - 1; j >= 0; j--) {
  36.                         if(a[j] == b[i]&&j<i) {
  37.                             swap(a[i], a[j]);
  38.                             swaps.push_back({i+1, j+1});
  39.                             time++;
  40.                             break;
  41.                         }
  42.                         else if(a[j] == b[i]&&b[j]!=b[i]){
  43.                         	swap(a[i], a[j]);
  44.                             swaps.push_back({i+1, j+1});
  45.                             time++;
  46.                             break;
  47.                         }
  48.                     }
  49.                 } else {
  50.                     int m;
  51.                     for(int j = n - 1; j >= 0; j--) {
  52.                         if(a[j] == 1&&j<i) {
  53.                             swap(a[i], a[j]);
  54.                             swaps.push_back({i+1, j+1});
  55.                             time++;
  56.                             break;
  57.                         }
  58.                         else if(a[j] == 1&&b[j]!=b[i]){
  59.                         	swap(a[i], a[j]);
  60.                             swaps.push_back({i+1, j+1});
  61.                             time++;
  62.                             break;
  63.                         }
  64.                     }
  65.                     for(int j = m; j >= 0; j--) {
  66.                         if(a[j] == b[i]&&j<i) {
  67.                             swap(a[i], a[j]);
  68.                             swaps.push_back({i+1, j+1});
  69.                             time++;
  70.                             break;
  71.                         }
  72.                         else if(a[j] == b[i]&&b[j]!=b[i]){
  73.                         	swap(a[i], a[j]);
  74.                             swaps.push_back({i+1, j+1});
  75.                             time++;
  76.                             break;
  77.                         }
  78.                     }
  79.                 }
  80.             }
  81.         }
  82.         cout << time << endl;
  83.         for (auto &p : swaps) {
  84.             cout << p.first << " " << p.second << endl;
  85.         }
  86.         for(int i = 0; i< n;i++){
  87.         	cout<<a[i]<<" ";
  88.         }
  89.         cout<<endl;
  90.     }   
  91. }
  92.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
3
4
0 2 0 1
3
1 2 0
15
1 2 0 1 2 0 0 1 2 1 1 0 1 2 0
stdout
copy 
2
4 2
3 2
0 0 1 2 
2
3 1
2 3
0 1 2 
12
15 13
13 11
12 10
11 15
10 13
9 12
7 4
6 1
5 11
5 1
2 10
1 15
0 1 0 0 0 1 1 1 1 2 2 2 0 2 1
https://ideone.com/R0dqca
language:
C++14 (gcc 8.3)
created:
3 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!