Untitled
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