Vaihdot

input/code.cpp: In function 'bool is_sorted()':
input/code.cpp:13:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(LL i = 1; i < v.size(); i++){
                   ~~^~~~~~~~~~
input/code.cpp: In function 'LL index_of(LL)':
input/code.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(LL i = 0; i < v.size(); i++) if(v[i] == x) return i;
                   ~~^~~~~~~~~~

#include <iostream>
#include <vector>
#include <utility>
//#include "stdlib_printing.hh"
 
using namespace std;
typedef long long LL;
 
vector<pair<LL,LL> > ans;
vector<LL> v;
 
bool is_sorted(){
    for(LL i = 1; i < v.size(); i++){
        if(v[i-1] > v[i]) return false;
    }
    return true;
}
 
LL index_of(LL x){
    for(LL i = 0; i < v.size(); i++) if(v[i] == x) return i;
    return -1; // Should not happen
}
 
void swap(LL i, LL j){
    ans.push_back({i+1,j+1});
    std::swap(v[i], v[j]);
}
 
void solve(){
    ans.clear();
    LL n; cin >> n;
    v.resize(n);
    for(LL i = 0; i < n; i++) {
        cin >> v[i]; v[i]--;
    }
    if(n <= 2){
        if(is_sorted()){
            cout << 0 << "\n"; return;
        } else{
            cout << -1 << "\n"; return;
        }
    }
    if(n == 3){
        if(v[1] != 1){
            cout << -1 << "\n"; return;
        }
        if(is_sorted()){
            cout << 0 << "\n"; return;
        } else{
            cout << 1 << "\n" << "1 3\n"; return;
        }
    }
 
    // n >= 4. Solution always exists
    // First put v[1] in place. 
    // Then put i = 2,...,n-2 in place by swapping through i = 0. 
    // Then swap i = 0 and i = n-1 if needed.
    LL i1 = index_of(1);
    if(i1 == 1){
        // Do nothing
    } else if(i1 == 0){
        swap(0,n-1); swap(n-1,1);
    } else if(i1 == 2){
        swap(2,0); swap(0,n-1), swap(n-1,1);
    } else{
        swap(1,i1);
    }
 
    for(LL x = 2; x <= n-2; x++){
        swap(index_of(x), 0);
        swap(0,x);
    }
    if(!is_sorted()) swap(0,n-1);
    cout << ans.size() << "\n";
    for(auto P : ans) cout << P.first << " " << P.second << "\n";
 
}
 
int main(int argc, char** argv){
    LL t; cin >> t; while(t--) solve();
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED