CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Vaihdot
Sender:jnalanko
Submission time:2020-10-16 18:32:27 +0300
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED65
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.05 s2details

Compiler report

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;
                   ~~^~~~~~~~~~

Code

#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 details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
1000
1
1
2
1 2
...

correct output
0
0
-1
0
-1
...

user output
0
0
-1
0
-1
...

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
79
49 42 77 41 37 61 46 55 7 72 4...

correct output
81
67 79
70 78
3 77
60 76
...

user output
153
2 45
16 1
1 3
29 1
...