Järjestäminen

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

int arr[100001]; //arr
int pos[100001]; //i to p
int n;
int chk(){
    for(int i = 1; i <= n; i++){
        if(i != arr[i]){
            return i-1;
        }
    }
    return n;
}
bool swp(int a, int b){
    if(a < 0) return 0;
    swap(arr[a], arr[b]);
    pos[arr[a]] = a;
    pos[arr[b]] = b;

    swap(arr[a+1], arr[b+1]);
    pos[arr[a+1]] = a+1;
    pos[arr[b+1]] = b+1;
    return 1;
}
int main(){
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> n;
        for(int p = 1; p <= n; p++){
            int t;
            cin >> t;
            arr[p] = t;
            pos[t] = p;
        }
        int s = chk();

        while(s < n){
            int t = s+1;
            if(pos[t] == t){
                s++;
                continue;
            }
            int apos = pos[t];
            if(apos < n){
                swp(apos, t);
            } else {
                if(s < n-1){
                    if(n-s > 4){
                        swp(apos,apos-2);
                    } else {
                        cout << "NO\n";
                        break;
                    }
                } else {
                    cout << "NO\n";
                }
            }
        }
        if(s == n){
            cout << "YES\n";
        }
    }
}

Test 1

Group: 1, 2

Verdict: OUTPUT LIMIT EXCEEDED

Test 2

Group: 2

Verdict: OUTPUT LIMIT EXCEEDED

Test 3

Group: 1, 2

Verdict: OUTPUT LIMIT EXCEEDED

Test 4

Group: 1, 2

Verdict: OUTPUT LIMIT EXCEEDED