Vaihdot

input/code.cpp: In function 'bool sorted(std::__cxx11::string)':
input/code.cpp:9:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < str.size(); i++) {
                     ~~^~~~~~~~~~~~
input/code.cpp: In function 'void bfs(int)':
input/code.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < queue.size(); i++) {
                     ~~^~~~~~~~~~~~~~
input/code.cpp: In function 'void testCase()':
input/code.cpp:91:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); i++) {
                         ~~^~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;

int a[1000];

bool sorted(string str) {
    for (int i = 1; i < str.size(); i++) {
        if (str[i] < str[i-1]) return false;
    }
    return true;
}


void bfs(int n) {
    map<string,string> prev;
    map<string,pair<int,int>> move;
    set<string> seen;
    string str = "";
    for (int i = 0; i < n; i++) str += to_string(a[i]);
    prev[str] = "";
    seen.insert(str);
    vector<string> queue;
    queue.push_back(str);
    for (int i = 0; i < queue.size(); i++) {
        str = queue[i];
        if (sorted(str)) {
            vector<pair<int,int>> v;
            while (prev[str] != "") {
                v.push_back(move[str]);
                str = prev[str];
            }
            cout << v.size() << "\n";
            for (int i = v.size()-1; i >= 0; i--) {
                cout << v[i].first << " " << v[i].second << "\n";
            }
            return;
        }
        for (int j = 0; j < n; j++) {
            for (int k = j+2; k < n; k++) {
                string uusi = str;
                swap(uusi[j],uusi[k]);
                if (!seen.count(uusi)) {
                    seen.insert(uusi);
                    move[uusi] = {j+1,k+1};
                    prev[uusi] = str;
                    queue.push_back(uusi);
                }
            }
        }
    }
    cout << -1 << "\n";
}

void testCase() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (n < 5) {
        bfs(n);
    } else {
        vector<pair<int,int>> v;
        for (int i = 0; i < n; i++) {
            if (a[i] == i+1) continue;
            int ind = 0;
            for (int j = 0; j < n; j++) {
                if (a[j] == i+1) {
                    ind = j;
                    break;
                }
            }
            if (ind == i+1) {
                if (i >= 2) {
                    v.push_back({1,ind+1});
                    v.push_back({1,i+1});
                    v.push_back({1,ind+1});
                } else {
                    v.push_back({n,ind+1});
                    v.push_back({n,i+1});
                    v.push_back({n,ind+1});
                }
                swap(a[ind],a[i]);
            } else {
                swap(a[ind],a[i]);
                v.push_back({ind+1, i+1});
            }
            
        }
        cout << v.size() << "\n";
        for (int i = 0; i < v.size(); i++) {
            cout << v[i].first << " " << v[i].second << "\n";
        }
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        testCase();
    }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED