Submission #19560370

---

Source Code Expand

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef WA_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

using ll  = long long;
using vi  = vector<int>;
using ull = unsigned long long;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=int(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=int(a);i>=(int)(b);i--)
const int mod  = 1e9+7;
const int inf  = 0x3f3f3f3f;
const int maxn = 1e5+10;
int main() {
#ifndef WA_DEBUG
    ios::sync_with_stdio(false);cin.tie(nullptr);
#endif
    int n;
    cin>>n;
    vector<int> pos(n+1),ans,a(n+1);
    vector<bool> vis(n);
    rep(i,1,n) {
        int x;
        cin>>x;
        a[i]=x;
        pos[x]=i;
    }
    bool f=true;
    rep(i,1,n) {
        if(pos[i]==i) continue;
        while(pos[i]!=i) {
            int pre=pos[i]-1;
            int val=a[pre];
            if(vis[pre]) {
                f=false;
                break;
            }
            ans.pb(pos[i]-1);
            vis[pre]=true;
            swap(a[pos[i]],a[pre]);
            pos[i]--;
            pos[val]++;
        }
        if(!f) break;
    }
    if(f) {
        for(int x:ans) cout<<x<<'\n';
    }
    else cout<<-1<<'\n';
    return 0;
}

Submission Info

Judge Result