[AOJ] No. 0385 ボゾソート

2019年12月19日

問題

方針

数列の要素を交換するたびに全ての要素が昇順に調べるのは効率が悪いので別の方法を考えます。昇順に整列させたときの数列と元の数列の要素が異なるものの数を \( t \) とします。交換を行う前に、\( t = 0 \) であれば、既に昇順に整列されています。\( 1 \) 回の命令で \( t \) の値を計算するには、命令の前後で交換された要素と昇順に整列された数列の要素と比べれば良いです。

また、\( 1 \) 回の命令で \( t \) の値は、\( -2, -1, 0, 1, 2 \) のどれかの値だけ変動することになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int a[N];
    vector<int> b(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin(), b.end());
    int Q;
    cin >> Q;
    int x[Q], y[Q];
    for (int i = 0; i < Q; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] != b[i]) cnt++;
    }
    if (cnt == 0) {
        cout << "0\n";
        return 0;
    }
    for (int i = 0; i < Q; i++) {
        int k = 0;
        if (a[x[i]] != b[x[i]]) k++;
        if (a[y[i]] != b[y[i]]) k++;
        int t = a[x[i]];
        a[x[i]] = a[y[i]];
        a[y[i]] = t;
        if (a[x[i]] != b[x[i]]) k--;
        if (a[y[i]] != b[y[i]]) k--;
        cnt -= k;
        if (cnt == 0) {
            cout << i + 1<< "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}