1 solutions

  • 0
    @ 2025-12-29 9:52:01
    #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