Submission #19560406


Source Code Expand

Copy
#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(pre);
            vis[pre]=true;
            swap(a[pos[i]],a[pre]);
            pos[i]--;
            pos[val]++;
        }
        if(!f) break;
    }
    rep(i,1,n-1) {
        if(!vis[i]) f=false;
    }
    if(f) {
        for(int x:ans) cout<<x<<'\n';
    }
    else cout<<-1<<'\n';
    return 0;
}

Submission Info

Submission Time
Task C - Exoswap
User WA_King
Language C++ (GCC 9.2.1)
Score 500
Code Size 1983 Byte
Status AC
Exec Time 46 ms
Memory 5860 KB

Judge Result

Set Name All Sample after_contest
Score / Max Score 500 / 500 0 / 0 0 / 0
Status
AC × 59
AC × 2
AC × 1
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_53.txt, testcase_54.txt, testcase_55.txt, testcase_56.txt, testcase_57.txt, testcase_6.txt, testcase_7.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
after_contest after_contest_1.txt
Case Name Status Exec Time Memory
after_contest_1.txt AC 9 ms 3636 KB
sample_01.txt AC 2 ms 3596 KB
sample_02.txt AC 2 ms 3628 KB
testcase_1.txt AC 3 ms 3584 KB
testcase_10.txt AC 2 ms 3868 KB
testcase_11.txt AC 24 ms 4608 KB
testcase_12.txt AC 14 ms 4304 KB
testcase_13.txt AC 15 ms 4100 KB
testcase_14.txt AC 46 ms 5832 KB
testcase_15.txt AC 41 ms 5676 KB
testcase_16.txt AC 44 ms 5796 KB
testcase_17.txt AC 43 ms 5784 KB
testcase_18.txt AC 42 ms 5724 KB
testcase_19.txt AC 41 ms 5720 KB
testcase_2.txt AC 10 ms 3628 KB
testcase_20.txt AC 42 ms 5672 KB
testcase_21.txt AC 44 ms 5788 KB
testcase_22.txt AC 41 ms 5832 KB
testcase_23.txt AC 44 ms 5648 KB
testcase_24.txt AC 44 ms 5860 KB
testcase_25.txt AC 41 ms 5700 KB
testcase_26.txt AC 44 ms 5796 KB
testcase_27.txt AC 43 ms 5756 KB
testcase_28.txt AC 35 ms 5176 KB
testcase_29.txt AC 11 ms 3632 KB
testcase_3.txt AC 2 ms 3504 KB
testcase_30.txt AC 42 ms 5656 KB
testcase_31.txt AC 39 ms 5564 KB
testcase_32.txt AC 17 ms 3932 KB
testcase_33.txt AC 36 ms 5404 KB
testcase_34.txt AC 30 ms 5808 KB
testcase_35.txt AC 32 ms 5700 KB
testcase_36.txt AC 29 ms 5724 KB
testcase_37.txt AC 28 ms 5784 KB
testcase_38.txt AC 27 ms 5808 KB
testcase_39.txt AC 32 ms 5696 KB
testcase_4.txt AC 9 ms 3504 KB
testcase_40.txt AC 34 ms 5652 KB
testcase_41.txt AC 13 ms 4032 KB
testcase_42.txt AC 20 ms 5372 KB
testcase_43.txt AC 28 ms 5352 KB
testcase_44.txt AC 29 ms 5364 KB
testcase_45.txt AC 30 ms 5840 KB
testcase_46.txt AC 30 ms 5424 KB
testcase_47.txt AC 32 ms 5468 KB
testcase_48.txt AC 27 ms 5832 KB
testcase_49.txt AC 24 ms 5428 KB
testcase_5.txt AC 6 ms 3476 KB
testcase_50.txt AC 29 ms 4872 KB
testcase_51.txt AC 13 ms 4020 KB
testcase_52.txt AC 10 ms 3812 KB
testcase_53.txt AC 11 ms 3776 KB
testcase_54.txt AC 43 ms 5784 KB
testcase_55.txt AC 44 ms 5796 KB
testcase_56.txt AC 29 ms 4768 KB
testcase_57.txt AC 30 ms 5700 KB
testcase_6.txt AC 10 ms 3472 KB
testcase_7.txt AC 3 ms 3500 KB
testcase_8.txt AC 3 ms 3592 KB
testcase_9.txt AC 34 ms 5296 KB