1 solutions
-
0
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define rep(i, n) for(ll i=0; i<(n); ++i) #define rrep(i, n) for(ll i=(n)-1, i>=0; --i) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define debug(x) cerr << #x << " : " << (x) << '\n' ll const INF = 2e18; // 4近傍 右上左下 const int dx4[4] = {1,0,-1,0}; const int dy4[4] = {0,1,0,-1}; // 8近傍 const int dx8[8] = {1,1,0,-1,-1,-1,0,1}; const int dy8[8] = {0,1,1,1,0,-1,-1,-1}; // grid内ならtrueを返し、gridから出るときはfalse bool in_grid(ll H, ll W, ll x, ll y){ return(0<=x&&x<H&&0<=y&&y<W); } template <typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << "," << p.second << ")"; } template <typename T> void print_vector(const std::vector<T>& x) { std::cerr << "["; for (size_t i = 0; i < x.size(); ++i) { std::cerr << x[i]; if (i != x.size() - 1) std::cerr << " "; } std::cerr << "]" << std::endl; } template <typename T> void print_vector2(const std::vector<std::vector<T>>& x) { for (const auto& row : x) { std::cerr << "["; for (size_t j = 0; j < row.size(); ++j) { std::cerr << row[j]; if (j != row.size() - 1) std::cerr << " "; } std::cerr << "]" << std::endl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); freopen("random_20.in","r",stdin); freopen("random_20.out","w",stdout); ll N; cin >> N; vector<ll> A(N); vector<ll> inv_A(N); // inv_A[val] = idx : A[idx] = valとなる for(ll i=0; i<N; i++){ cin >> A[i]; A[i]--; inv_A[A[i]] = i; } vector<pair<ll, ll>> ans; for(ll i=0; i<N-1; i++){ if(A[i] == i) continue; ll target = inv_A[i]; ans.emplace_back(i, target); swap(inv_A[A[i]], inv_A[A[target]]); swap(A[i], A[target]); } ll M = ans.size(); cout << M << endl; for(ll i=0; i<M; i++){ cout << ans[i].first+1 << " " << ans[i].second+1 << '\n'; } return 0; }
- 1
Information
- ID
- 2045
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- (None)
- # Submissions
- 2
- Accepted
- 1
- Uploaded By