Untitled

 avatar
unknown
plain_text
13 days ago
3.9 kB
2
Indexable
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <time.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#include <assert.h>
#include <map>
#include <math.h>
#include <functional>
#include <set>
#include <unordered_map>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <complex>
#include <list>
#include <stack>
#include <deque>
#include <chrono>
#include <unordered_set>
#include <unordered_set>
#pragma GCC optimize("Ofast,03","unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse4")

using namespace std;

#define Chris "queue"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define MARK(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define emp emplace_back
#define fi first
#define se second
#define MIN(x,y) if (x > (y)) x = (y)
#define MAX(x,y) if (x < (y)) x = (y)
#define mp make_pair
#define mem(v, a) memset((v), (a), sizeof((v)))
#define MINE(v) *min_element(All(v))
#define MAXE(v) *max_element(All(v))
#define el "\n"
#define dd(a, n, m, x) vector<vector<int>> (a)((n), vector<int>((m), (x)))
#define mu2(a) (1 << ((a)))
#define bitcount(a) __builtin_popcountll(a)
#define Chris_ signed main()
#define faster ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define showTime() cerr << '\n' << "Running time: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef set<int> sii;
typedef map<int, int> mii;
typedef stack<int> sti;
typedef deque<int> dqi;
typedef queue<int> quei;
typedef unordered_map<int, int> umii;
typedef unordered_set<int, int> umsii;

const ll mod = 1e9 + 7;
const int inf = (int) 1e5 + 5;
const int LOG = (int) 20;
const int base = (int) 131;
const ll m2 = 1LL * mod * mod;

#define cong(a, b, m) ((((a) % (m)) + ((b) % (m))) % (m))
#define tru(a, b, m) ((((a) % (m)) - ((b) % (m))) % (m))
#define nhan(a, b, m) ((((a) % (m)) * ((b) % (m))) % (m))

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n;

struct data
{
    ll v;
    int id;
};

void nhap()
{
    cin >> n;
}

void solve()
{
    nhap();
    vll a(n);
    FOR(i, 0, n)
    {
        cin >> a[i];
    }
    vector<data> node(n);
    FOR(i, 0, n)
    {
        node[i] = {a[i], i};
    }
    sort(all(node), [](const data &A, const data &B)
    {
        if(A.v == B.v) return A.id < B.id;
        return A.v < B.v;
    });
    vii sorted(n);
    FOR(i, 0, n)
    {
        sorted[node[i].id] = i;
    }
    vector<bool> visited(n, false);
    vector<pii> swaps;
    FOR(i, 0, n)
    {
        if(visited[i] || sorted[i] == i) continue;
        int cur = i;
        vii c;
        while(!visited[cur])
        {
            visited[cur] = true;
            c.pb(cur);
            cur = sorted[cur];
        }
        FOR(j, 1, c.size())
        {
            swaps.pb({c[0] + 1, c[j] + 1});
            swap(a[c[0]], a[c[j]]);
        }
    }
    for(auto &p : swaps)
    {
        cout << p.fi << " " << p.se << el;
    }
}

Chris_
{
    faster
    file(Chris)

    solve();

    showTime();

    return 0;
}
Editor is loading...
Leave a Comment