fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void solve() {
  6.     int n;
  7.     cin >> n;
  8.     vector<int> a(n);
  9.     // Count of each number and their positions
  10.     int count2 = 0, count1 = 0, count0 = 0;
  11.     vector<int> pos0, pos1, pos2;
  12.  
  13.     for(int i = 0; i < n; i++) {
  14.         cin >> a[i];
  15.         if(a[i] == 0) {
  16.             count0++;
  17.             pos0.push_back(i);
  18.         }
  19.         else if(a[i] == 1) {
  20.             count1++;
  21.             pos1.push_back(i);
  22.         }
  23.         else {
  24.             count2++;
  25.             pos2.push_back(i);
  26.         }
  27.     }
  28.  
  29.     vector<pair<int,int>> moves;
  30.     int target = n-1;
  31.  
  32.     // Only process 2s if we have any
  33.     if(count2 > 0) {
  34.         while(target >= n - count2) {
  35.             if(a[target] != 2) {
  36.                 if(a[target] == 1) {
  37.                     // Direct swap from 1 to 2
  38.                     moves.push_back({target + 1, pos2.back() + 1});
  39.                     a[target] = 2;
  40.                     a[pos2.back()] = 1;
  41.                     pos1.push_back(pos2.back());
  42.                     pos2.pop_back();
  43.                 } else { // a[target] == 0
  44.                     // Two moves: 0->1->2
  45.                     moves.push_back({target + 1, pos1.back() + 1});
  46.                     moves.push_back({pos1.back() + 1, pos2.back() + 1});
  47.                     a[target] = 2;
  48.                     a[pos1.back()] = 0;
  49.                     a[pos2.back()] = 1;
  50.                     pos0.push_back(pos1.back());
  51.                     pos1.pop_back();
  52.                     pos1.push_back(pos2.back());
  53.                     pos2.pop_back();
  54.                 }
  55.             }
  56.             target--;
  57.         }
  58.     }
  59.  
  60.     // After handling all 2s, process remaining 1s
  61.     while(target >= n - count2 - count1) {
  62.         if(a[target] == 0) {
  63.             moves.push_back({target + 1, pos1.back() + 1});
  64.             a[target] = 1;
  65.             a[pos1.back()] = 0;
  66.             pos0.push_back(pos1.back());
  67.             pos1.pop_back();
  68.         }
  69.         target--;
  70.     }
  71.  
  72.     cout << moves.size() << "\n";
  73.     for(const auto& move : moves) {
  74.         cout << move.second << " " << move.first << "\n";
  75.     }
  76. }
  77.  
  78. int main() {
  79.     ios::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.  
  82.     int t;
  83.     cin >> t;
  84.     while(t--) {
  85.         solve();
  86.     }
  87.     return 0;
  88. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3
4
0 2 0 1
3
1 2 0
6
0 1 1 2 2 2
stdout
copy 
2
2 4
2 3
2
1 3
2 1
0
https://ideone.com/JtlbH7
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!