Submission #1156074

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

template<class T,T op(T,T)> class segtree{
public:
    int n,size_;
    vector<T> dat;
    T id_;
    segtree()=default;
    segtree(int size,T id,T initial_value){ init(size,id,initial_value); }
    void init(int size,T id,T initial_value){
        size_=size;
        id_=id;
        n=1;
        while(n<size) n*=2;
        dat.assign(2*n-1,id);
        for(int i=0; i<size; ++i) update(i,initial_value);
    }
    int size()const{ return size_; }
    void update(int k, T a) {
        k+=n-1; // leaf
        dat[k]=a;
        while(k>0) {
            k=(k-1)/2;
            dat[k]=op(dat[k*2+1],dat[k*2+2]);
        }
    }
    T at(int index){ return dat[index+n-1]; }
    void add(int k,T a){ update(k,op(at(k),a)); }
    T query(int a,int b) { return query(a,b,0,0,n); }
    T query(int a,int b,int k,int l,int r) {
        if(r<=a or b<=l) return id_;
        if(a<=l and r<=b) return dat[k];
        int m=(l+r)/2;
        return op(query(a,b,k*2+1,l,m),query(a,b,k*2+2,m,r));
    }
};

int add(int a,int b){
    return a+b;
}

void solve(){
    int n;
    cin >> n;
    vector<int> a(n),b(n),f(n),g(n);
    rep(i,0,n){
        cin >> a[i];
        --a[i];
        --b[i];
        f[a[i]]=i;
        g[i]=a[i];
        a[i]=i;
    }
    rep(i,0,n){
        cin >> b[i];
        --b[i];
        b[i]=f[b[i]];
    }

    i64 d=0;
    segtree<int,add> seg(n,0,0);
    rep(i,0,n){
        d+=i-seg.query(0,b[i]);
        seg.update(b[i],1);
    }

    if(d==0 or d%2==1){
        cout << -1 << endl;
        return;
    }

    i64 d_=0;
    seg.init(n,0,0);
    rep(i,0,n){
        i64 tmp=i-seg.query(0,b[i]);
        if(d_+tmp>=d/2){
            sort(b.begin(),b.begin()+i);
            for(int j=i; j>0; --j){
                if(b[j]<b[j-1]){
                    swap(b[j],b[j-1]);
                    ++d_;
                    if(d_==d/2){
                        rep(k,0,n) cout << g[b[k]]+1 << (k==n-1?'\n':' ');
                        return;
                    }
                }
            }
        }else d_+=tmp;
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Judge Result