Submission #55020028

---

Source Code Expand

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define sz(a) ((long long)(a).size())
#define X first
#define Y second
 
using ll = long long;
using ull = unsigned long long;
using dbl = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll myRandMod) {
    return (ull)rng() % myRandMod;
}
 
const ll INF = 1e9;
const ll LINF = 1e18;
const int MOD = (int)1e9 + 7;
const int MAXN = 505;

bool t[MAXN][MAXN];
 
void solve() {
    memset(t, 0, sizeof t);
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    vector<int> pos(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
        pos[p[i]] = i;
    }
    vector<pair<int, int>> ans;


    // for (int i = 1; i < n; ++i) {
    //     bool ok = true;
    //     while (ok) {
    //         ok = false;
    //         for (int x = n - 1; x >= 0; --x) {
    //             int y = x - i;
    //             if (y < 0) {
    //                 continue;
    //             }
    //             int px = pos[x];
    //             int py = pos[y];
    //             if (k > py - px || t[px][py]) {
    //                 continue;
    //             }
    //             ok = true;
    //             t[px][py] = 1;
    //             swap(pos[x], pos[y]);
    //             swap(p[px], p[py]);
    //             ans.push_back({px, py});
    //             break;
    //         }
    //     }
    // }



    bool ok0 = true;
    while (ok0) {
        ok0 = false;
        for (int i = 1; i < n && !ok0; ++i) {
            // bool ok = true;
            // while (ok) {
                // ok = false;
                for (int x = 0; x < n; ++x) {
                // for (int x = n - 1; x >= 0; --x) {
                    int y = x - i;
                    if (y < 0) {
                        continue;
                    }
                    int px = pos[x];
                    int py = pos[y];
                    if (k > py - px || t[px][py]) {
                        continue;
                    }
                    // ok = true;
                    ok0 = true;
                    t[px][py] = 1;
                    swap(pos[x], pos[y]);
                    swap(p[px], p[py]);
                    ans.push_back({px, py});
                    break;
                }
            // }
        }
    }

    cout << ans.size() << "\n";
    for (auto [x, y] : ans) {
        cout << x + 1 << " " << y + 1 << "\n";
    }
}
 
signed main() {
#ifdef LOCAL
    assert(freopen("in.txt", "r", stdin));
    assert(freopen("out.txt", "w", stdout));
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
 
    int T = 1;
    // cin >> T;
    for (int numt = 0; numt < T; ++numt) {
        solve();
    }
 
#ifdef LOCAL
    cout << endl << endl << "time = " << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
}

Submission Info

Judge Result